Information Technology Reference
In-Depth Information
Proof:
By Lemma 2, it is possible to construct in
O
(
2
) time a level-connected in-
stance (
V
,E
,ʳ
,T
) of CL-P
LANARITY
that is cl-planar if and only if (
V,E,ʳ,T
)
is cl-planar, with
|
V
|
|
V
|
=
O
(
|
V
|
2
). By Lemma 3, it is possible to construct in
O
(
|
V
|
)
time a proper instance (
V
,E
,ʳ
,
-level planar
if and only if (
V
,E
,ʳ
,T
) is cl-planar. Finally, by Theorem 3, it is possible to test in
O
(
T
) of
T
-L
EVEL
P
LANARITY
that is
T
V
|
2
) time whether (
V
,E
,ʳ
,
T
) is
|
T
-level planar.
4 Open Problems
Several problems are opened by this research:
1. The algorithms for testing level planarity [10] and for testing cl-planarity for level-
connected proper hierarchies [9] both have linear-time complexity. Althoughour
algorithms solve more general problems than the ones above, they are less efficient.
This leaves room for future research aiming at improving our complexity bounds.
2. Our
NP
-hardness result on the complexity of CL-P
LANARITY
exploits a cluster
hierarchy whose depth is linear in the number of vertices of the underlyinggraph.
Does the
NP
-hardness hold if the cluster hierarchy is flat?
3. The
-hardness of CL-P
LANARITY
is, to the best of our knowledge, the first
hardness result for a variation of the clustered planarity problem in which none
of the c-planarity constraints is dropped. Is it possible to use similar techniques to
tackle the problem of determining the complexity of C
LUSTERED
P
LANARITY
?
NP
Acknowledgments.
Work partially supported by ESF EuroGIGA GraDR, by the Aus-
tralian Research Council (grant DE140100708), by the MIUR project AMANDA “Al-
gorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT 001, and by EU
FP7STREP ”Leone: From Global Measurements to Local Management”, no. 317647.
References
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 2014. LNCS, vol. 8344, pp. 200-212. Springer, Heidel-
berg (2014)
5. Blasi us, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamas-
sia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)
6. Blasius, 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, Heidel-
berg (2013)
7. Blasius, 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 hierar-
chical graphs and clustered graphs. Algorithmica 44(1), 1-32 (2006)
