
354 Simultaneous Embedding of Planar Graphs
354 Simultaneous Embedding of Planar Graphs
[BCD
+
07] [BCD
+
07] [BCD
+
07]
[BCD
+
07] [BCD
+
07] [B CD
+
07] [BCD
+
07]
[CvKL
+
11]
[DEK04]
[CvKL
+
11]
[CvKL
+
11]
[AGKN12]
[CEBFK09]
[FKK09] [AGKN12]
[BCD
+
07, EK05a] [CvKL
+
11]
[GKV09]
[CvKL
+
11]
[BCD
+
07] [BCD
+
07] [BCD
+
07]
instances always having an SGE
G
1
& G
2
caterpillar
3n × 3 n
examples without an SGE
G
1
path
k stars
O ( n ) × O(n)
G
1
path & G
2
ext. star
O ( n
2
) × O( n )
G
1
& G
2
tree
G
1
depth-4 tree & G
2
edge disj. path
G
1
matching six matchings
G
1
path, G
2
edge disj.
G
1
& G
2
planar G
1
& G
2
outerplanar three paths
G
1
& G
2
path
n × n
G
1
& G
2
cycle
4n × 4 n
G
1
caterpillar & G
2
path
n × 2n
G
1
wheel & G
2
cycle
G
1
outerpath & G