Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time

Eades, Peter and Hong, Seok-Hee and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 339-345 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_30).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_30
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:1322

Repository Staff Only: item control page

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)