Abstract
A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.
In this extended abstract, proofs are omitted. For the full version of this paper, see [4]. This work was initiated at the Workshop on Geometric Graph Theory 2011, June, Port Douglas, Australia, organized by Peter Eades and Seok-Hee Hong, and funded by the University of Sydney. Peter Eades and Seok-Hee Hong are partially supported by the Australian Research Council. Giuseppe Liotta is partially supported by MIUR of Italy under project Algo-DEEP prot. 2008TFBWL4; Pascal Schweitzer is supported by the National Research Fund, Luxembourg and co-funded under the Marie Curie Actions of the European Commission FP7-COFUND.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Auer, C., Brandenburg, F.J., Gleißner, A., Reislhuber, J.: On 1-planar graphs with rotation systems. Tech. Rep. MIP1207, Faculty of Informatics and Mathematics, University of Passau (2012)
Borodin, O.V.: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs. Metody Diskret. Analiz. 41, 12–26, 108 (1984)
Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. CoRR abs/1203.5944 (2012)
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. TR IT-IVG-2012-02, School of IT, University of Sydney (2012)
Eades, P., Liotta, G.: Right Angle Crossing Graphs and 1-Planarity. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 148–153. Springer, Heidelberg (2012)
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)
Hudák, D., Madaras, T.: On local properties of 1-planar graphs with high minimum degree. Ars Math. Contemp. 4(2), 245–254 (2011)
Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory (2012)
Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)
Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29, 107–117 (1965)
Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discrete Mathematics 310(1), 6–11 (2010)
Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM J. Discrete Math. 24(4), 1527–1540 (2010)
Thomassen, C.: Rectilinear drawings of graphs. Journal of Graph Theory 12(3), 335–341 (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eades, P., Hong, SH., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y. (2013). Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)