On the Complexity of Clustered-Level Planarity and T-Level Planarity

Preprint English OPEN
Angelini, Patrizio ; Da Lozzo, Giordano ; Di Battista, Giuseppe ; Frati, Fabrizio ; Roselli, Vincenzo (2014)
  • Subject: Computer Science - Computational Geometry | Computer Science - Data Structures and Algorithms

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.
  • References (13)
    13 references, page 1 of 2

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

    2. 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)

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

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

    5. Blasiu¨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)

    6. Bla¨sius, T., Rutter, I.: Disconnectivity and relative positions in simultaneous embeddings. In: Didimo, W., Patrignani, M. (eds.) GD'13. LNCS, vol. 7704, pp. 31-42 (2013)

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

    8. 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)

    9. Forster, M., Bachmaier, C.: Clustered level planarity. In: van Emde Boas, P., Pokorny´, J., Bielikova´, M., Stuller, J. (eds.) SOFSEM. LNCS, vol. 2932, pp. 218-228 (2004)

    10. Ju¨nger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 67-113 (2002)

  • Metrics
    No metrics available
Share - Bookmark