Complexity of geometric \(k\)-planarity for fixed \(k\). (English) Zbl 1452.05180
Summary: The rectilinear local crossing number, \(\overline{\mathrm{lcr}}(G)\), of a graph \(G\) is the smallest \(k\) so that \(G\) has a straight-line drawing with at most \(k\) crossings along each edge. We show that deciding whether \(\overline{\mathrm{lcr}}(G)\leq k\) for a fixed \(k\) is complete for the existential theory of the reals, \(\exists \mathbb{R}\).
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | B. M. ´Abrego, K. Dondzila, S. Fern´andez-Merchant, E. Lagoda, S. Sajjadi, and Y. Sapozhnikov. On the rectilinear local crossing number ofKm,n.Journal of Information Processing, 25:542-550, August 2017. · doi:10.2197/ipsjjip.25.542 |
| [2] | B. M. ´Abrego and S. Fern´andez-Merchant. The rectilinear local crossing number ofKn.J. Combin. Theory Ser. A, 151:131-145, 2017. · Zbl 1366.05073 · doi:10.1016/j.jcta.2017.04.003 |
| [3] | C. Auer, F. J. Brandenburg, A. Gleißner, and J. Reislhuber. 1-planarity of graphs with a rotation system.Journal of Graph Algorithms and Applications, 19(1):67-86, 2015. · Zbl 1307.05057 |
| [4] | D. Bienstock and N. Dean. Bounds for rectilinear crossing numbers.J. Graph Theory, 17(3):333-348, 1993. · Zbl 0777.05049 · doi:10.1002/jgt.3190170308 |
| [5] | S. Cabello and B. Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard.SIAM Journal on Computing, 42(5):1803-1829, 2013. · Zbl 1282.05033 · doi:10.1137/ |
| [6] | J. Canny. Some algebraic and geometric computations in pspace. InSTOC ’88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460-469, New York, NY, USA, 1988. ACM. · doi:10.1145/62212.62257 |
| [7] | T. M. Chan, F. Frati, C. Gutwenger, A. Lubiw, P. Mutzel, and M. Schaefer. Drawing partially embedded and simultaneously planar graphs.J. Graph Algorithms Appl., 19(2):681-706, 2015. · Zbl 1328.05130 · doi:10.7155/jgaa.00375 |
| [8] | W. Didimo, G. Liotta, and F. Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1-37, 2019. · doi:10.1145/3301281 |
| [9] | A. Grigoriev and H. L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge.Algorithmica, 49(1):1-11, 2007. · Zbl 1131.68120 · doi:10.1007/s00453-007-0010-x |
| [10] | F. Harary and A. Hill. On the number of crossings in a complete graph.Proc. Edinburgh Math. Soc. (2), 13:333-338, 1962/1963. · Zbl 0118.18902 · doi:10.1017/S0013091500025645 |
| [11] | C. Hern´andez-V´elez, J. Lea˜nos, and G. Salazar. On the pseudolinear crossing number.J. Graph Theory, 84(3):297-310, 2017. · Zbl 1359.05085 · doi:10.1002/jgt.22027 |
| [12] | S.-H. Hong and T. Tokuyama, editors.Beyond Planar Graphs, Communications of NII Shonan Meetings. Springer, 2020. · Zbl 1465.68020 · doi:10.1007/978-981-15-6533-5 |
| [13] | V. Jel´ınek, J. Kratochv´ıl, and I. Rutter. A Kuratowski-type theorem for planarity of partially embedded graphs.Comput. Geom., 46(4):466-492, 2013. · Zbl 1259.05044 · doi:10.1016/j.comgeo.2012.07. |
| [14] | P. C. Kainen. Thickness and coarseness of graphs.Abh. Math. Sem. Univ. Hamburg, 39:88-95, 1973. · Zbl 0264.05108 · doi:10.1007/BF02992822 |
| [15] | S. G. Kobourov, G. Liotta, and F. Montecchiani. An annotated bibliography on 1-planarity. Comput. Sci. Rev., 25:49-67, 2017. · Zbl 1398.68402 · doi:10.1016/j.cosrev.2017.06.002 |
| [16] | V. P. Korzhik and B. Mohar. Minimal obstructions for 1-immersions and hardness of 1planarity testing.J. Graph Theory, 72(1):30-71, 2013. · Zbl 1259.05046 |
| [17] | J. Kratochv´ıl and J. Matouˇsek. NP-hardness results for intersection graphs.Comment. Math. Univ. Carolin., 30(4):761-773, 1989. · Zbl 0697.05052 |
| [18] | J. Matouˇsek. Intersection graphs of segments and∃R.ArXiv e-prints, 2014. (last accessed 6/10/2020). |
| [19] | N. E. Mn¨ev. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. InTopology and geometry—Rohlin Seminar, volume 1346 of Lecture Notes in Math., pages 527-543. Springer, Berlin, 1988. · Zbl 0667.52006 · doi:10.1007/BFb0082792 |
| [20] | J. Richter-Gebert. Mn¨ev’s universality theorem revisited.S´em. Lothar. Combin., 34:15, 1995. · Zbl 0855.05041 |
| [21] | M. Schaefer. Complexity of some geometric and topological problems. InGraph drawing, volume 5849 ofLecture Notes in Comput. Sci., pages 334-344. Springer, Berlin, 2010. · Zbl 1284.68305 |
| [22] | M. Schaefer. The graph crossing number and its variants: A survey.The Electronic Journal of Combinatorics, 20:1-90, 2013. Dynamic Survey, #DS21, last updated September 2020. · Zbl 1267.05180 · doi:10.37236/2713 |
| [23] | M. Schaefer. Picking planar edges; or, drawing a graph with a planar subgraph. InGraph drawing, volume 8871 ofLecture Notes in Comput. Sci., pages 13-24. Springer, Heidelberg, 2014. · Zbl 1426.68224 · doi:10.1007/978-3-662-45803-7_2 |
| [24] | M. Schaefer. On the complexity of some geometric problems with fixed parameters. Submitted to JGAA, 2020. |
| [25] | P. W. Shor. Stretchability of pseudolines is NP-hard. InApplied geometry and discrete mathematics, volume 4 ofDIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 531- 554. Amer. Math. Soc., Providence, RI, 1991. · Zbl 0751.05023 · doi:10.1090/dimacs/004/41 |
| [26] | J. C. Urschel and J. Wellens. Testing gapk-planarity is NP-complete.ArXiv e-prints, 2020. (last accessed 1/2/2021). IntroductionContextBounded Rectilinear Local Crossing Number IThe Gadget NkNP-Hardness of Geometric k-PlanarityBounded Rectilinear Local Crossing Number IIArrangements of Pseudo-SegmentsA PuzzleProof of Theorem 1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
