Article

Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph

Author:

Marcus SchaeferAuthors Info & Claims

GD 2014: Revised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 8871

Pages 13 - 24

https://doi.org/10.1007/978-3-662-45803-7_2

Published: 24 September 2014 Publication History

Abstract

Given a graph G and a subset F⊆EG of its edges, is there a drawing of G in which all edges of F are free of crossings? We show that this question can be solved in polynomial time using a Hanani-Tutte style approach. If we require the drawing of G to be straight-line, but allow up to one crossing along each edge in F, the problem turns out to be as hard as the existential theory of the real numbers.

References

[1]

Angelini, P., Binucci, C., Da Lozzo, G., Didimo, W., Grilli, L., Montecchiani, F., Patrignani, M., Tollis, I.G.: Drawings of non-planar graphs with crossing-free subgraphs. In: Wismath, S., Wolff, A. eds. GD 2013. LNCS, vol. 8242, pp. 292---303. Springer, Heidelberg 2013

Digital Library

[2]

Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 202---221. Society for Industrial and Applied Mathematics, Philadelphia 2010

Digital Library

[3]

Angelini, P., Da Lozzo, G., Neuwirth, D.: On some $\mathcal{NP}$-complete SEFE problems. In: Pal, S.P., Sadakane, K. eds. WALCOM 2014. LNCS, vol. 8344, pp. 200---212. Springer, Heidelberg 2014

[4]

Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM Journal on Computing 425, 1803---1829 2013

[5]

Canny, J.: Some algebraic and geometric computations in pspace. In: STOC 1988: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 460---469. ACM, New York 1988

Digital Library

[6]

Chojnacki, C. Hanani, H.: Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae 23, 135---142 1934

[7]

de Longueville, M.: A course in topological combinatorics. Universitext. Springer, New York 2013

[8]

Eggleton, R.B.: Rectilinear drawings of graphs. Utilitas Math. 29, 149---172 1986

[9]

Eppstein, D.: Big batch of graph drawing preprints, http://11011110.livejournal.com/275238.html last accessed September 4, 2013

[10]

Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 491, 1---11 2007

Digital Library

[11]

Gutwenger, C., Mutzel, P., Schaefer, M.: Practical experience with Hanani-Tutte for testing c-planarity. In: McGeoch, C.C., Meyer, U. eds. 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments ALENEX, pp. 86---97. SIAM 2014

Digital Library

[12]

Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: Fáry's theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. eds. COCOON 2012. LNCS, vol. 7434, pp. 335---346. Springer, Heidelberg 2012

[13]

Jelínek, V., Kratochvíl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. 464, 466---492 2013

Digital Library

[14]

Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. In: Tollis, I.G., Patrignani, M. eds. GD 2008. LNCS, vol. 5417, pp. 302---312. Springer, Heidelberg 2009

Digital Library

[15]

Kratochvíl, J.: String graphs. I. The number of critical nonstring graphs is infinite. J. Combin. Theory Ser. B 521, 53---66 1991

Digital Library

[16]

Kratochvíl, J.: Crossing number of abstract topological graphs. In: Whitesides, S.H. ed. GD 1998. LNCS, vol. 1547, pp. 238---245. Springer, Heidelberg 1999

Digital Library

[17]

Mäkinen, E.: On circular layouts. International Journal of Computer Mathematics 241, 29---37 1988

[18]

Nagamochi, H.: Straight-line drawability of embedded graphs. Technical Report 2013-005, Kyoto University 2013

[19]

Pelsmajer, M.J., Schaefer, M., Štefankoviă, D.: Removing independently even crossings. SIAM Journal on Discrete Mathematics 242, 379---393 2010

Digital Library

[20]

Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. eds. GD 2009. LNCS, vol. 5849, pp. 334---344. Springer, Heidelberg 2010

Digital Library

[21]

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. Journal of Graph Algortihms and Applications 174, 367---440 2013

[22]

Schaefer, M.: Hanani-Tutte and related results. In: Bárány, I., Böröczky, K.J., Fejes Tóth, G., Pach, J. eds. Geometry--Intuitive, Discrete, and Convex--A Tribute to László Fejes Tóth. Bolyai Society Mathematical Studies, vol. 24. Springer, Berlin 2014

[23]

Schaefer, M., Sedgwick, E., Štefankoviă, D.: Recognizing string graphs in NP. In: Proceedings of the 33th Annual ACM Symposium on Theory of Computing STOC 2002 2002

Digital Library

[24]

Schaefer, M., Štefankoviă, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Unpublished manuscript 2009

[25]

Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied Geometry and Discrete Mathematics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, pp. 531---554. Amer. Math. Soc., Providence 1991

[26]

Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theory 123, 335---341 1988

[27]

Tutte, W.T.: Toward a theory of crossing numbers. J. Combinatorial Theory 8, 45---53 1970

[28]

Wikipedia. Existential theory of the reals 2012, http://en.wikipedia.org/wiki/Existential_theory_of_the_reals Online; accessed July 17, 2013

Cited By

Schaefer M(2021)-Drawability is -CompleteGraph Drawing and Network Visualization10.1007/978-3-030-92931-2_5(72-86)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92931-2_5
Angelini PBekos M(2019)Hierarchical Partial PlanarityAlgorithmica10.1007/s00453-018-0530-681:6(2196-2221)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-0530-6
Borrazzo MDa Lozzo GFrati FPatrignani M(2019)Graph Stories in Small AreaGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_41(545-558)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_41
Show More Cited By

Recommendations

Prescribed edges and forbidden edges for a cycle in a planar graph

In 1956, Tutte proved that a 4-connected planar graph is Hamiltonian. Moreover, in 1997, Sanders extended this to the result that a 4-connected planar graph contains a Hamiltonian cycle through any two of its edges. Harant and Senitsch [J. Harant, S. ...
Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs
Abstract
Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, ...
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GD 2014: Revised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 8871

September 2014

506 pages

ISBN:9783662458020

Editors:
Christian Duncan
Quinnipiac University, Hamden, USA
,
Antonios Symvonis
National Technical University of Athens, Athens, Greece

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 24 September 2014

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schaefer M(2021)-Drawability is -CompleteGraph Drawing and Network Visualization10.1007/978-3-030-92931-2_5(72-86)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92931-2_5
Angelini PBekos M(2019)Hierarchical Partial PlanarityAlgorithmica10.1007/s00453-018-0530-681:6(2196-2221)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-0530-6
Borrazzo MDa Lozzo GFrati FPatrignani M(2019)Graph Stories in Small AreaGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_41(545-558)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_41
Lozzo GRutter I(2015)Planarity of Streamed GraphsProceedings of the 9th International Conference on Algorithms and Complexity - Volume 907910.1007/978-3-319-18173-8_11(153-166)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1007/978-3-319-18173-8_11

View Options

View options

Media

Figures

Other

Tables

View Table of Contents