An algorithm for the graph crossing number problem

Julia Chuzhoy

Type: Article

Publication Date: 2011-06-06

Citations: 36

DOI: https://doi.org/10.1145/1993636.1993678

Locations

arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	An Algorithm for the Graph Crossing Number Problem	2010	Julia Chuzhoy
+	An Algorithm for the Graph Crossing Number Problem	2010	Julia Chuzhoy
+ PDF Chat	A subpolynomial approximation algorithm for graph crossing number in low-degree graphs	2022	Julia Chuzhoy Zihan Tan
+	On Graph Crossing Number and Edge Planarization	2010	Julia Chuzhoy Yury Makarychev Anastasios Sidiropoulos
+	Towards Better Approximation of Graph Crossing Number	2020	Julia Chuzhoy Sepideh Mahabadi Zihan Tan
+	A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs	2022	Julia Chuzhoy Zihan Tan
+ PDF Chat	A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs	2022	Julia Chuzhoy Zihan Tan
+	On topological graphs with at most four crossings per edge	2015	Eyal Ackerman
+ PDF Chat	Towards Better Approximation of Graph Crossing Number	2020	Julia Chuzhoy Sepideh Mahabadi Zihan Tan
+	On topological graphs with at most four crossings per edge	2015	Eyal Ackerman
+ PDF Chat	On Graph Crossing Number and Edge Planarization	2011	Julia Chuzhoy Yury Makarychev Anastasios Sidiropoulos
+	Computing crossing number in linear time	2007	Ken‐ichi Kawarabayashi Buce Reed
+	Crossing Number for Graphs With Bounded Pathwidth	2016	Thérèse Biedl Markus Chimani Martin Derka Petra Mutzel
+	Crossing Number for Graphs With Bounded Pathwidth	2016	Thérèse Biedl Markus Chimani Martin Derka Petra Mutzel
+ PDF Chat	Crossing Number is NP-hard for Constant Path-width (and Tree-width)	2024	Petr Hliněný Liana Khazaliya
+	On the Maximum Crossing Number	2017	Markus Chimani Stefan Felsner Stephen Kobourov Torsten Ueckerdt Pável Valtr Alexander Wolff
+ PDF Chat	A Survey on Graph Drawing Beyond Planarity	2019	Walter Didimo Giuseppe Liotta Fabrizio Montecchiani
+ PDF Chat	Cutwidth and Crossings	2025	J. Rauch Dieter Rautenbach
+	Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs	2015	Patrizio Angelini Carla Binucci Giordano Da Lozzo Walter Didimo Luca Grilli Fabrizio Montecchiani Maurizio Patrignani Ioannis G. Tollis
+	Maximum Cut Parameterized by Crossing Number	2020	Markus Chimani Christine Dahn Martina Juhnke‐Kubitzke Nils M. Kriege Petra Mutzel Alexander Nover

Works That Cite This (27)

Action	Title	Year	Authors
+	Approximating the rectilinear crossing number	2019	Jacob Fox János Pach Andrew Suk
+ PDF Chat	A tighter insertion-based approximation of the crossing number	2016	Markus Chimani Petr Hliněný
+	Towards Better Approximation of Graph Crossing Number	2020	Julia Chuzhoy Sepideh Mahabadi Zihan Tan
+ PDF Chat	A Tighter Insertion-Based Approximation of the Crossing Number	2011	Markus Chimani Petr Hliněný
+ PDF Chat	Approximation Algorithms for Euler Genus and Related Problems	2013	Chandra Chekuri Anastasios Sidiropoulos
+ PDF Chat	Crossing Numbers and Stress of Random Graphs	2018	Markus Chimani Hanna Döring Matthias Reitzner
+	Computational topology of graphs on surfaces	2017	Éric Colin de Verdière
+ PDF Chat	Crossing minimization in perturbed drawings	2020	Radoslav Fulek Csaba D. Tóth
+ PDF Chat	An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL	2022	Fedor V. Fomin Petr A. Golovach Giannos Stamoulis Dimitrios M. Thilikos
+	A Pseudo-approximation for the Genus of Hamiltonian Graphs	2013	Yury Makarychev Amir Nayyeri Anastasios Sidiropoulos

Works Cited by This (8)

Action	Title	Year	Authors
+	Computing crossing number in linear time	2007	Ken‐ichi Kawarabayashi Buce Reed
+ PDF Chat	Computing crossing numbers in quadratic time	2001	Martin Grohe
+ PDF Chat	Expander flows, geometric embeddings and graph partitioning	2009	Sanjeev Arora Satish Rao Umesh Vazirani
+	None	2007	Felix Lazebnik Oleg Pikhurko Andrew J. Woldar
+	Crossing Number Problems	1973	Paul Erdős R. Kent Guy
+	A combinatorial problem	1946	de Ng Dick Bruijn
+	Computing crossing numbers in quadratic time	2003	Martin Grohe
+	Congruent Graphs and the Connectivity of Graphs	1932	Hassler Whitney