Abstract
A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are on the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time and specialize 1-planar graphs, whose recognition is \(\mathcal{NP}\)-hard.
Our main result is a linear-time algorithm that first tests whether a graph G is o1p, and then computes an embedding. Moreover, the algorithm can augment G to a maximal o1p graph. If G is not o1p, then it includes one of six minors (see Fig. 3), which are also detected by the recognition algorithm. Hence, the algorithm returns a positive or negative witness for o1p.
This work was supported in part by the Deutsche Forschungsgemeinschaft (DFG) grant Br835/18-1.
A linear-time algorithm for testing outer 1-planarity was independently obtained by Hong et al. and appears in these proceedings [14].
Chapter PDF
Similar content being viewed by others
References
Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line drawings of 3-connected 1-planar graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 83–94. Springer, Heidelberg (2013)
Auer, C., Brandenburg, F.J., Gleißner, A., Reislhuber, J.: On 1-planar graphs with rotation systems. Tech. Rep. MIP 1207, University of Passau (2012)
Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 97–108. Springer, Heidelberg (2013)
Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 327–338. Springer, Heidelberg (2013)
Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. Tech. Rep. arXiv:1203.5944 (cs.CG), Computing Research Repository (CoRR) (March 2012)
Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. Internat. J. Comput. Geom. Appl. 22(6), 543–558 (2012)
Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996)
Eades, P., Hong, S.H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: Testing maximal 1-planarity of graphs with a rotation system in linear time. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 339–345. Springer, Heidelberg (2013)
Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 148–153. Springer, Heidelberg (2011)
Eggleton, R.B.: Rectilinear drawings of graphs. Utilitas Math. 29, 149–172 (1986)
Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)
Hliněný, P.: Crossing number is hard for cubic graphs. J. Combin. Theory, Ser. B 96(4), 455–471 (2006)
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.H., Eades, P., Naoki, K., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 71–82. Springer, Heidelberg (2013)
Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersion and hardness of 1-planarity testing. J. Graph Theor. 72, 30–71 (2013)
Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inform. Process. Lett. 9(5), 229–232 (1979)
Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. aus dem Math. Seminar der Univ. Hamburg 29, 107–117 (1965)
Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theor. 12(3), 335–341 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Auer, C. et al. (2013). Recognizing Outer 1-Planar Graphs in Linear Time. In: Wismath, S., Wolff, A. (eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242. Springer, Cham. https://doi.org/10.1007/978-3-319-03841-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-03841-4_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03840-7
Online ISBN: 978-3-319-03841-4
eBook Packages: Computer ScienceComputer Science (R0)