Crossing Numbers and Combinatorial Characterization of Monotone Drawings of $$K_n$$ K n

Martin Balko, Radoslav Fulek, Jan Kynčl

Type: Article

Publication Date: 2014-11-15

Citations: 34

DOI: https://doi.org/10.1007/s00454-014-9644-z

View Publication

Download PDF

Locations

Discrete & Computational Geometry - View
arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Bounding the number of crossings for a particular class of drawings of $K_{n,n}$	2019	Carolina Medina Irene Parada Gelasio Salazar Birgit Vogtenhuber
+	More on the crossing number of : Monotone drawings	2013	Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández‐Merchant Pedro Ramos Gelasio Salazar
+ PDF Chat	On the Maximum Number of Crossings in Star-Simple Drawings of $$K_n$$ with No Empty Lens	2020	Stefan Felsner Michael M. Hoffmann Kristin Knorr Irene Parada
+ PDF Chat	Monotone Drawings of k-Inner Planar Graphs	2018	Anargyros Oikonomou Antonios Symvonis
+ PDF Chat	Note on k-planar crossing numbers	2017	János Pach Łászló A. Székely Csaba D. Tóth Gézá Tóth
+ PDF Chat	Monotone Drawings of Planar Graphs	2002	János Pach Gézá Tóth
+ PDF Chat	On the crossing profile of rectilinear drawings of $K_n$	2025	I.L. Chen Oriol Solé-Pi
+	The 2-page crossing number of $K_n$	2012	Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández‐Merchant Pedro M. Ramos Gelasio Salazar
+	The 2-page crossing number of $K_n$	2012	Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández‐Merchant Pedro Ramos Gelasio Salazar
+	The crossing numbers of $K_m\times P_n$ and $K_m\times C_n$	2012	Yuansheng Yang Baigong Zheng Xirong Xu Xiaohui Lin
+	Shellable drawings and the cylindrical crossing number of $K_n$	2013	Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández‐Merchant Pedro Ramos Gelasio Salazar
+	The crossing numbers of $K_{n,n}-nK_2$, $K_{n}\times P_2$, $K_{n}\times P_3$ and $K_n\times C_4$	2012	Yuansheng Yang Baigong Zheng Xiaohui Lin Xirong Xu
+ PDF Chat	Counting the number of crossings in geometric graphs	2020	Frank Duque Ruy Fabila‐Monroy César Hernández-Vélez Carlos Hidalgo-Toscano
+ PDF Chat	Crossing numbers of beyond-planar graphs	2021	Markus Chimani Philipp Kindermann Fabrizio Montecchiani Pável Valtr
+ PDF Chat	Crossing Numbers of Beyond-Planar Graphs	2019	Markus Chimani Philipp Kindermann Fabrizio Montecchiani Pável Valtr
+	Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs	2023	Oswin Aichholzer Joachim Orthaber Birgit Vogtenhuber
+ PDF Chat	Crossing Number for Graphs with Bounded Pathwidth	2020	Thérèse Biedl Markus Chimani Martin Derka Petra Mutzel
+ PDF Chat	Plane Spanning Trees in Edge-Colored Simple Drawings of $$K_{n}$$	2020	Oswin Aichholzer Michael M. Hoffmann Johannes Obenaus Rosna Paul Daniel Perz Nadja Seiferth Birgit Vogtenhuber Alexandra Weinberger
+ PDF Chat	The Crossing Number of Seq-Shellable Drawings of Complete Graphs	2018	Petra Mutzel Lutz Oettershagen
+	On $(\le k)$-edges, crossings, and halving lines of geometric drawings of $K_n$	2011	Bernardo M. Ábrego M. Cetina Silvia Fernández‐Merchant Jesús Leaños Gelasio Salazar

Works That Cite This (25)

Action	Title	Year	Authors
+ PDF Chat	On the Maximum Number of Crossings in Star-Simple Drawings of $$K_n$$ with No Empty Lens	2020	Stefan Felsner Michael M. Hoffmann Kristin Knorr Irene Parada
+ PDF Chat	Topological Drawings Meet Classical Theorems from Convex Geometry	2020	Helena Bergold Stefan Felsner Manfred Scheucher Felix Schröder Raphael Steiner
+ PDF Chat	Edge-Minimum Saturated k-Planar Drawings	2021	Steven Chaplick Fabian Klute Irene Parada Jonathan Rollin Torsten Ueckerdt
+	A superlinear lower bound on the number of 5-holes	2020	Oswin Aichholzer Martin Balko Thomas Hackl Jan Kynčl Irene Parada Manfred Scheucher Pável Valtr Birgit Vogtenhuber
+	Two disjoint 5-holes in point sets	2020	Manfred Scheucher
+ PDF Chat	Simple Realizability of Complete Abstract Topological Graphs Simplified	2020	Jan Kynčl
+ PDF Chat	Topological Drawings Meet Classical Theorems from Convex Geometry	2022	Helena Bergold Stefan Felsner Manfred Scheucher Felix Schröder Raphael Steiner
+	Bounding the tripartite-circle crossing number of complete tripartite graphs	2019	Charles Camacho Silvia Fernández‐Merchant Marija Jelić Milutinović Rachel Kirsch Linda Kleist Elizabeth Bailey Matson Jennifer White
+	Remarks on the structure of simple drawings of $K_n$	2020	R. Bruce Richter Matthew Sullivan
+	Edge-Minimum Saturated k-Planar Drawings	2020	Steven Chaplick Fabian Klute Irene Parada Jonathan Rollin Torsten Ueckerdt

Works Cited by This (15)

Action	Title	Year	Authors
+	More on the crossing number of : Monotone drawings	2013	Bernardo M. Ábrego Oswin Aichholzer Silvia Fernández‐Merchant Pedro Ramos Gelasio Salazar
+	Clusters of stars	1997	Ileana Streinu
+ PDF Chat	Crossing Numbers and Combinatorial Characterization of Monotone Drawings of $$K_n$$ K n	2014	Martin Balko Radoslav Fulek Jan Kynčl
+	Semispaces of configurations, cell complexes of arrangements	1984	Jacob E. Goodman Richard Pollack
+	Sweeps, arrangements and signotopes	2001	Stefan Felsner Helmut Weil
+	Proof of a conjecture of Burr, Grünbaum, and Sloane	1980	Jacob E. Goodman
+ PDF Chat	On the Number of Crossings in a Complete Graph	1963	Frank Harary Anthony Hill
+ PDF Chat	New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn	2007	Oswin Aichholzer Jesús Garcı́a David Orden Pedro Ramos
+	None	2007	Felix Lazebnik Oleg Pikhurko Andrew J. Woldar
+ PDF Chat	Computer solution to the 17-point Erdős-Szekeres problem	2006	G Szekeres Lindsay Peters