Upward Planarity Testing of Embedded Mixed Graphs

Binucci, Carla and Didimo, Walter (2012) Upward Planarity Testing of Embedded Mixed Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 427-432 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_40).

Full text not available from this repository.

Abstract

A mixed graph has both directed and undirected edges. We study an upward planarity testing problem for embedded mixed graphs and solve it using Integer Linear Programming. Experiments show the efficiency of our technique.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_40
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.840 Upward
ID Code:1275

Repository Staff Only: item control page

References

Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn.Springer, Heidelberg (2009)

Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 6(12), 476–497 (1994)

Binucci, C., Didimo, W., Giordano, F.: Maximum upward planar subgraphs of embedded planar digraphs. Comput. Geom. 41(3), 230–246 (2008)

Didimo, W.: Upward planar drawings and switch-regularity heuristics. Journal of Graph Algorithms and Applications 10(2), 259–285 (2006)

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discrete Math. 23(4), 1842–1899 (2009)

Didimo, W., Pizzonia, M.: Upward embeddings and orientations of undirected planar graphs.Journal of Graph Algorithms and Applications 7(2), 221–241 (2003)

Eiglsperger, M., Eppinger, F., Kaufmann, M.: An approach for mixed upward planarization. Journal of Graph Algorithms and Applications 7(2), 203–220 (2003)

Garg, A., Tamassia, R.: Upward planarity testing. Order 12, 109–133 (1995)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing 31(2), 601–625 (2001)