Abstract
A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Unfortunately, testing the 1-planarity of a graph is known as NP-complete.
This paper initiates the study of the problem of the testing 2-planarity of a graph, in particular, testing the “full-outer-2-planarity” of a graph. A graph is outer-2-planar, if it admits an outer-2-planar embedding, that is every vertex is on the outer boundary and no edge has more than two crossings. A graph is fully-outer-2-planar, if it admits a fully-outer-2-planar embedding, that is an outer-2-planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and fully-outer-2-planar graphs, and prove that triconnected fully-outer-2-planar graphs have a constant number of fully-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing the fully-outer-2-planarity of a graph G, whose vertex-connectivity is 1, 2 or at least 3. The algorithm also produces a fully-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every fully-outer-2-planar embedding admits a straight-line drawing.
For omitted proofs and figures, see the full version of this paper TR [17].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41(3), 365–375 (2009)
Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1–9 (1997)
Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is NP-hard. J. Graph Algorithms Appl. 16(2), 569–597 (2012)
Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Recognizing outer 1-planar graphs in linear time. GD 107–118, 2014 (2013)
Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S.-H., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 198–209. Springer, Heidelberg (2014)
Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Tollis, I.G.: Fan-planar graphs: combinatorial properties and complexity results. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 186–197. Springer, Heidelberg (2014)
Cheong, O., Har-Peled, S., Kim, H., Kim, H.-S.: On the number of edges of fan-crossing free graphs. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 163–173. Springer, Heidelberg (2013)
Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996)
Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011)
Eades, P., Hong, S.-H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65–76 (2013)
Fox, J., Pach, J., Suk, A.: The number of edges in \(k\)-quasi-planar graphs. SIAM J. Discrete Math. 27(1), 550–561 (2013)
Fáry, I.: On straight line representations of planar graphs. Acta Sci. Math. Szeged 11, 229–233 (1948)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)
Hong, S., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 49(1), 1–11 (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)
Hong, S., Nagamochi, H.: Beyond planarity: testing full outer-2-planarity in linear time. Technical report [2014-003], Department of Applied Mathematics and Physics, Kyoto University (2014)
Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs, CoRR abs/1403.6184 (2014)
Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theor. 72(1), 30–71 (2013)
Nagamochi, H.: Straight-line drawability of embedded graphs. Technical report [2013-005], Department of Applied Mathematics and Physics, Kyoto University (2013)
Pach, J., Toth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)
Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theor. 12(3), 335–341 (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hong, SH., Nagamochi, H. (2016). Testing Full Outer-2-planarity in Linear Time. In: Mayr, E. (eds) Graph-Theoretic Concepts in Computer Science. WG 2015. Lecture Notes in Computer Science(), vol 9224. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53174-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-662-53174-7_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53173-0
Online ISBN: 978-3-662-53174-7
eBook Packages: Computer ScienceComputer Science (R0)