The Importance of Being Proper

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio and Roselli, Vincenzo (2014) The Importance of Being Proper. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 246-258 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_21).

Full text not available from this repository.

Abstract

In this paper we study two problems related to the drawing of level graphs, that is, T -Level Planarity and Clustered-Level Planarity. We show that both problems are NP -complete in the general case and that they become polynomial-time solvable when restricted to proper instances.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_21
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.700 Layering
M Methods > M.999 Others
P Styles > P.180 Cluster
P Styles > P.480 Layered
P Styles > P.540 Planar
Z Theory > Z.750 Topology
ID Code:1437

Repository Staff Only: item control page

References

Angelini, P., Da Lozzo, G., Neuwirth, D.: On the complexity of some problems related to SEFE. CoRR abs/1207.3934 (2013)

Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. J. of Discrete Algorithms 14, 150–172 (2012)

Angelini, P., Da Lozzo, G.: Deepening the relationship between SEFE and C-planarity. CoRR abs/1404.6175 (2014)

Angelini, P., Da Lozzo, G., Neuwirth, D.: On some NP -complete SEFE problems. In: Pal, S.P., Sadakane, K. (eds.) WALCOM 2014. LNCS, vol. 8344, pp. 200–212. Springer, Heidelberg (2014)

Blasiüs, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)

Bläsius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 31–42. Springer, Heidelberg (2013)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: Khanna, S. (ed.) SODA, pp. 1030–1043. SIAM (2013)

Eades, P., Feng, Q.W., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)

Forster, M., Bachmaier, C.: Clustered level planarity. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 218–228. Springer, Heidelberg (2004)

Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1999)

Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111–114 (1979)

Schaefer, M.: Toward a theory of planarity: Hanani-Tutte and planarity variants. J. of Graph Alg. and Appl. 17(4), 367–440 (2013)

Wotzlaw, A., Speckenmeyer, E., Porschen, S.: Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation. Discrete Applied Mathematics 160(16-17), 2349–2363 (2012)