Graph Simultaneous Embedding Tool, GraphSET

Estrella-Balderrama, Alejandro and Fowler, J. Joseph and Kobourov, Stephen G. (2009) Graph Simultaneous Embedding Tool, GraphSET. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 169-180 (Official URL:

Full text not available from this repository.


Problems in simultaneous graph drawing involve the layout of several graphs on a shared vertex set. This paper describes a Graph Simultaneous Embedding Tool, GraphSET, designed to allow the investigation of a wide range of embedding problems. GraphSET can be used in the study of several variants of simultaneous embedding including simultaneous geometric embedding, simultaneous embedding with fixed edges and colored simultaneous embedding with the vertex set partitioned into color classes. The tool has two primary uses: (i) studying theoretical problems in simultaneous graph drawing through the production of examples and counterexamples and (ii) producing layouts of given classes of graphs using built-in implementations of known algorithms. GraphSET along with movies illustrating its utility are available at

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_17
Classifications:S Software and Systems > S.001 General
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:906

Repository Staff Only: item control page


Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)

Brandes, U., Erten, C., Fowler, J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S., Liotta, G., Mutzel, P., Symvonis, A.: Colored simultaneous geometric embeddings. In: COCOON 2007. LNCS, vol. 4598, pp. 254–263 (2007)

Dietz, P., Leigh, D.: Diamondtouch: a multi-user touch technology. In: 14th ACM Symposium on User interface software and technology. pp. 219–226 (2001)

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

Erten, C., Kobourov, S.G., Navabia, A., Le, V.: Simultaneous graph drawing: Layout algorithms and visualization schemes. In: GD 2003. LNCS, vol. 2912, pp. 437– 449, Springer, Heidelberg (2004)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. In: GD 2006. LNCS, vol. 4372, pp. 367–369, Springer, Heidelberg (2007)

Estrella-Balderrama, A., Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: GD 2007. LNCS, vol. 4875, pp. 280–290, Springer, Heidelberg (2008)

Fowler, J.J., Kobourov, S.G.: Minimum level nonplanar patterns for trees. In: GD 2007. LNCS, vol. 4875, pp. 69–75 (2008)

Gassner, E., Jünger, M., Percan, M.,Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: WG 2006. LNCS, vol. 4271, pp. 325–335, Springer, Heidelberg (2006)

Geyer, M., Kaufmann, M., Vrto, I.: Two trees which are self-intersecting when o drawn simultaneously. In: GD 2005. LNCS, vol. 3843, pp. 201–210, Springer, Heidelberg (2006)

Healy, P., Harrigan, M.: Practical level planarity testing and layout with embedding constraints. In: GD 2007. LNCS, vol. 4875, pp. 62–68, Springer, Heidelberg (2008)

Healy, P., Kuusik, A.: The vertex-exchange graph: A new concept for multi-level crossing minimisation. In: GD 1999. LNCS, vol. 1731, pp. 205–216, Springer, Heidelberg (1999)

Jünger, M., Leipert, S.: Level planar embedding in linear time. In: GD 1999, LNCS, vol. 1731, pp. 72–81 (1999)

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

Kobourov, S.G., Pitta, C.: An interactive multi-user system for simultaneous graph drawing. In: GD 2004.LNCS, vol. 3383, pp. 492–501 Springer, Heidelberg (2004)

Mehlhorn, K., Näher, S.: The LEDA Platform of Combinatorial and Geometric a Computing. Cambridge University Press (1999)