2-Layer Fan-Planarity: From Caterpillar to Stegosaurus

Binucci, Carla and Chimani, Markus and Didimo, Walter and Gronemann, Martin and Klein, Karsten and Kratochvíl, Jan and Montecchiani, Fabrizio and Tollis, Ioannis G. (2015) 2-Layer Fan-Planarity: From Caterpillar to Stegosaurus. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 281-294 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_24).

Full text not available from this repository.

Abstract

In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.480 Layered
P Styles > P.540 Planar
ID Code:1496

Repository Staff Only: item control page

References

Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S.-H., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 198–209. Springer, Heidelberg (2014)

Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Symvonis, A., Tollis, I.G.: Fan-planarity: properties and complexity. Theor. Comput. Sci. 589, 76–86 (2015)

Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-trees. J. Comput. Syst. Sci. 13, 335–379 (1976)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)

Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. Algorithmica 68(4), 954–997 (2014)

Di Giacomo, E., Didimo, W., Grilli, L., Liotta, G., Romeo, S.A.: Heuristics for the maximum 2-layer RAC subgraph problem. Comput. J. 58(5), 1085–1098 (2015)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011)

Didimo, W., Liotta, G.: The crossing angle resolution in graph drawing. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 167–184. Springer, New York (2012)

Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: ACSC 1986, pp. 327–334 (1986)

Eades, P., Kelly, D.: Heuristics for drawing 2-layered networks. Ars Comb. 21, 89–98 (1986)

Eades, P., Whitesides, S.: Drawing graphs in two layers. Theor. Comput. Sci. 131(2), 361–374 (1994)

Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)

Huang, W., Eades, P., Hong, S.: Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25(4), 452–465 (2014)

Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1, 1–25 (1997)

Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR abs/1403.6184 (2014). http://​arxiv.​org/​abs/​1403.​6184

Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. SIAM J. Optim. 11(4), 1065–1080 (2001)

Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific, Singapore (2002)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109–125 (1981)

Valls, V., Martí, R., Lino, P.: A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs. Eur. J. Oper. Res. 90(2), 303–319 (1996)