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

Schaefer, Marcus (2014) Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_2).

Full text not available from this repository.

Abstract

Given a graph G and a subset F ⊆ E(G) 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_2
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.600 Poly-line
P Styles > P.720 Straight-line
Z Theory > Z.750 Topology
ID Code:1418

Repository Staff Only: item control page

References

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)

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)

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

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

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)

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

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

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

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

Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)

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)

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)

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

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)

Kratochvíl, J.: String graphs. I. The number of critical nonstring graphs is infinite. J. Combin. Theory Ser. B 52(1), 53–66 (1991)

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)

Mäkinen, E.: On circular layouts. International Journal of Computer Mathematics 24(1), 29–37 (1988)

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

Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Removing independently even crossings. SIAM Journal on Discrete Mathematics 24(2), 379–393 (2010)

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)

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. Journal of Graph Algortihms and Applications 17(4), 367–440 (2013)

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)

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)

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

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)

Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theory 12(3), 335–341 (1988)

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

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