Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs

Alam, Muhammed Jawaherul and Brandenburg, Franz J. and Kobourov, Stephen G. (2013) Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 83-94 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_8).

Full text not available from this repository.

Abstract

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.720 Straight-line
ID Code:1363

Repository Staff Only: item control page

References

Bárány, I., Rote, G.: Strictly convex drawings of planar graphs. Documenta Mathematica 11, 369–391 (2006)

Bárány, I., Tokushige, N.: The minimum area of convex lattice n-gons. Combinatorica 24(2), 171–185 (2004)

Baybars, I.: On k-path hamiltonian maximal planar graphs. Discrete Mathematics 40(1), 119–121 (1982)

Bodendiek, R., Schumacher, H., Wagner, K.: Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abh. aus dem Math. Seminar der Univ. Hamburg 53, 41–52 (1983)

Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. Algorithmica 47(4), 399–420 (2007)

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)

Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions. In: Symposium on Computational Geometry, pp. 319–328 (1996)

Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry and Applications 7(3), 211–223 (1997)

Didimo, W.: Density of straight-line 1-planar graph drawings. Information Processing Letter 113(7), 236–240 (2013)

Dolev, D., Leighton, T., Trickey, H.: Planar embedding of planar graphs. In: Advances in Computing Research, pp. 147–161 (1984)

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)

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

Erten, C., Kobourov, S.G.: Simultaneous embedding of a planar graph and its dual on the grid. Theory of Computing Systems 38(3), 313–327 (2005)

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

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)

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)

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

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

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

Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) Symposium on Discrete Algorithms, pp. 138–148 (1990)

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

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

Tutte, W.T.: How to draw a graph. Proc. London Math. Society 13(52), 743–768 (1963)