Information Technology Reference
In-Depth Information
Conjecture 1.
If
G
T
is acyclic and
(
G, T
)
admits an independently even clustered
drawing then
(
G, T
)
is c-planar.
A variant of the conjecture when
G
T
is a path would provide a polynomial time algo-
rithm for c-planarity testing for strip clustered graph, which is an open problem stated
in [1]. Note that our proof from Section 5 fails if the graph has hexagonal faces. We
wonder if this difficulty can be overcome or rather could lead to
NP
-hardness.
Acknowledgements.
We a r e gratefultothenumerous anonymous reviewers for many
valuable comments.
References
1. Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing. In: Wismath, S.,
Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 37-48. Springer, Heidelberg (2013)
2. Biedl, T.C.: Drawing planar partitions III: Two constrained embedding problems. Technical
report, RUTCOR, Rutgers University (1998)
3. Cairns,
G.,
Nikolayevsky,
Y.:
Bounds
for generalized
thrackles.
Discrete
Comput.
Geom. 23(2), 191-206 (2000)
4. Chimani, M., Zeranski, R.: Upward planarity testing:Acomputational study. In: Wismath,
S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 13-24. Springer, Heidelberg (2013)
5. Cortese, P.F., Di Battista, G.: Clustered planarity (invited lecture). In: Twenty-First Annual
SymposiumonComputational Geometry (Proc. SoCG 2005), pp. 30-32. ACM (2005)
6. Cortese, P.F., Di Battista, G., Frati, F., Patrignani, M., Pizzonia, M.: C-planarity of c-
connected clustered graphs. J. Graph Algorithms Appl. 12(2), 225-262 (2008)
7. Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of
clusters. J. Graph Algorithms Appl. 9(3), 391-413 (2005)
8. Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms.
SIAM Journal on Computing 15(4), 948-957 (1986)
9. de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: Tremaux trees and planarity. International
Journal of Foundations of Computer Science 17(05), 1017-1029 (2006)
10. de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by Tremauxorders.
Combinatorica 5(2), 127-135 (1985)
11. Di Battista, G., Frati, F.: Efficient c-planarity testing for embedded flat clustered graphs with
small faces. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp.
291-302. Springer, Heidelberg (2008)
12. Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Junger, M., Reinelt,
G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570,
pp. 11-26. Springer, Heidelberg (2003)
13. Feng, Q.-W., Cohen, R.F., Eades, P.: How to draw a planar clustered graph. In: Li, M., Du,
D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 21-30. Springer, Heidelberg (1995)
14. Feng, Q.W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.)
ESA 1995. LNCS, vol. 979, pp. 213-226. Springer, Heidelberg (1995)
15. Fulek, R.: Towards Hanani-Tutte theorem for clustered graphs. In: 40th International Work-
shop on Graph-Theoretic Concepts in Computer Science (accepted)
16. Fulek, R., Kyncl, J., Malinovic, I., Palvolgyi, D.: Efficient c-planarity testing algebraically.
arXiv:1305.4519
