Logo

Login | Create Account

Convex Drawing for c-Planar Biconnected Clustered Graphs

Nagamochi, Hiroshi and Kuroya, Katsutoshi (2004) Convex Drawing for c-Planar Biconnected Clustered Graphs. [Conference Paper]

Full text not available from this repository.

Abstract

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph is a graph with a set of non-intersecting clusters. In this paper, we assume that the graph is planar, each non leaf cluster has exactly two child clusters in the tree representation of non-intersecting clusters, and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight line segments with no crossing between two edges, and (ii) the boundary of the biconnected subgraph induced by each cluster is convex polygon.

Item Type:Conference Paper
Classifications:P Styles > P.720 Straight-line
P Styles > P.180 Cluster
G Algorithms and Complexity > G.350 Clusters
ID Code:466
Deposited By:Selbach, Anna
Deposited On:09 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=369

Repository Staff Only: item control page

References

G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph drawing, Prentice Hall, 1999.

V. Batagelj, D. Kerzic and T. Pisanski, Automatic clustering of languages, Computational Linguistics, 18(3) 339-352, 1992.

E. Dahlhaus, Linear time algorithm to recognize clustered planar graphs and its parallelization (extended abstract), Latin America symposium on theoretical Informatics (LATIN'98), Lecture Notes in Computer Science, 1380, 239-248, 1998.

C. A. Duncan, M. T. Goodrich, and S. G. Kobourov, Planarity -preserving clustering and embedding for large planar graphs, Graph Drawing (GD '99), Lecture Notes in Computer Science, 1731, 186-196, 1999.

P. Eades, Q.-W. Feng and H. Nagamochi, Drawing clustered graphs on an orthogonal grid, Journal of Graph Algorithms and Application, 3(4), 3-29, 1999.

P. Eades, Q.-W. Feng, Drawing clustered graphs on orthogonal grid, Graph Drawing (GD '97), Lecture Notes in Computer Science, 1353, 146-157, 1997.

P. Eades, Q.-W. Feng, X. Lin, and H. Nagamochi, Straight-line drawing algorithms for hierarchical graphs and clustered graphs, Technical Report Newcastle University (submitted to a journal), 1999.

Q.-W. Feng, R.-F. Cohen and P. Eades, Planarity for clustered graphs, Algorithms (ESA '95), Lecture Notes in Computer Science, 979, 213-226, 1995.

E. Godehardt, Graphs as Structural Models, Advances in System Analysis 4, Vieweg, 1998.

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan and R. Weiskircher, Advances in c-planarity testing of clustered graphs (extended abstract), Graph Drawing (GD 2002), Lecture Notes in Computer Science, 2528, 220-235, 2002.

D. Harel and R. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Computing, 13, 338-355, 1984.

M. Kaufmann and D. Wagner, Drawing graphs, Lecture Notes in Computer Science, 2025, Springer, 2001.

T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, North-Holland Mathematics Studies 140/32, 1988.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.