Drawing Outer 1-planar Graphs with Few Slopes

Di Giacomo, Emilio and Liotta, Giuseppe and Montecchiani, Fabrizio (2014) Drawing Outer 1-planar Graphs with Few Slopes. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 174-185 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_15).

Full text not available from this repository.

Abstract

A graph is outer 1-planar if it admits a drawing where each vertex is on the outer face and each edge is crossed by at most another edge. Outer 1-planar graphs are a superclass of the outerplanar graphs and a subclass of the partial 3-trees. We show that an outer 1-planar graph G of bounded degree Δ admits an outer 1-planar straight-line drawing that uses O(Δ) different slopes, which extends a previous result by Knauer et al. about the planar slope number of outerplanar graphs (CGTA, 2014). We also show that O(Δ2) slopes suffice to construct a crossing-free straight-line drawing of G; the best known upper bound on the planar slope number of planar partial 3-trees of bounded degree Δ is O(Δ5) and is proved by Jelínek et al. (Graphs and Combinatorics, 2013).

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_15
Classifications:D Aesthetics > D.999 Others
G Algorithms and Complexity > G.420 Crossings
M Methods > M.900 Tree
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.750 Topology
ID Code:1431

Repository Staff Only: item control page

References

Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line grid 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., 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)

Barát, J., Matousek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. The Electronic Journal of Combinatorics 13(1) (2006)

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)

Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. International Journal on Computational Geometry and Applications 22(6), 543–558 (2012)

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM Journal on Computing 25(5), 956–997 (1996)

Di Giacomo, E., Liotta, G., Montecchiani, F.: The planar slope number of subcubic graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 132–143. Springer, Heidelberg (2014)

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

Dujmović, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Computational Geometry 38(3), 181–193 (2007)

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)

Hong, S.-H., Eades, P., Katoh, N., 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)

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)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesar, M., Vyskocil, T.: The planar slope number of planar partial 3-trees of bounded degree. Graphs and Combinatorics 29(4), 981–1005 (2013)

Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM Journal on Discrete Mathematics 27(2), 1171–1183 (2013)

Knauer, K.B., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. Computational Geometry 47(5), 614–624 (2014)

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)

Lenhart, W., Liotta, G., Mondal, D., Nishat, R.: Planar and plane slope number of partial 2-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 412–423. Springer, Heidelberg (2013)

Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. In: van Kreveld, M.J., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 254–265. Springer, Heidelberg (2011)

Pach, J., Pálvölgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. The Electronic Journal of Combinatorics 13(1) (2006)

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

Wade, G.A., Chu, J.-H.: Drawability of complete graphs using a minimal slope set. The Computer Journal 37(2), 139–142 (1994)