A Linear-Time Algorithm for Testing Outer-1-Planarity

Hong, Seok-Hee and Eades, Peter and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) A Linear-Time Algorithm for Testing Outer-1-Planarity. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 71-82 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_7).

Full text not available from this repository.


A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:1362

Repository Staff Only: item control page


Hong, S.H., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. TR-IT-IVG-2013-01. Technical Report, School of IT, University of Sydney (June 2013)

Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Recognizing outer 1-planar graphs in linear time. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 107–118. Springer, Heidelberg (2013)

Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29, 107–117 (1965)

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 (1984)

Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17, 427–439 (1997)

Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Mathematics 307, 854–865 (2007)

Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM J. Discrete Math. 24, 1527–1540 (2010)

Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. Journal of Graph Theory 72, 30–71 (2013)

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 - (extended abstract). In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 339–345. Springer, Heidelberg (2013)

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

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

Hong, S.H., Eades, P., Liotta, G., Poon, S.H.: Fáry’s theorem for 1-planar graphs. In: [19], pp. 335–346

Nagamochi, H.: Straight-line drawability of embedded graphs. Technical Report 2013-005, Department of Applied Mathematics and Physics, Kyoto University, Japan (2013)

Battista, G.D., Tamassia, R.: On-line maintenance of triconnected components with spqr-trees. Algorithmica 15, 302–318 (1996)

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)

Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geometry Appl. 22, 543–558 (2012)

Frati, F.: Straight-line drawings of outerplanar graphs in o(dn log n) area. Comput. Geom. 45, 524–533 (2012)

Knauer, K.B., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. In: [19], pp. 323–334

Gudmundsson, J., Mestre, J., Viglas, T. (eds.): COCOON 2012. LNCS, vol. 7434. Springer, Heidelberg (2012)