Advances in Testing C-Planarity of Embedded Flat Clustered Graphs
Advances on Testing C-Planarity of
Embedded Flat Clustered Graphs
Markus Chimani
(Osnabrück University)
Joint work with
Guiseppe Di Battista
(University Roma Tre)
Fabrizio Frati
(University of Sydney)
Karsten Klein
(Monash University)
Clustered Planarity (C-Planarity)
3
0
7
4
1
8
5
2
6
9
C = (
G,T
)
Complexity of c-planarity testing
c-connected:
O(|V|)
[Dahlhaus 98]
non c-connected:
P? NP?
open for ~20 years…
Complexity for special cases
Polynomial cases…
•
C-connected
[Feng et al. 95], [Dahlhaus 98]
•
Completely c-connected
[Cornelsen, Wagner 06]
•
Almost c-connected
[Gutwenger et al. 02]
•
Extrovert
[Goodrich et al. 05]
•
“Cycles of Clusters”
[Cortese et al. 05]
•
and many more…
Unfortunately, most cases are very restricted and/or unnatural…
Complexity even unknown for natural, seemingly simple subcases…
•
What if
G
is already
embedded
?
•
What if the cluster hierarchie is
flat
, i.e, only one level of clusters?
•
What if
both
?
Now:
Flat embedded clustered graphs
•
One level of clusters (= no nested clusters)
•
G
is embedded.
•
Does there exist a drawing of the cluster regions such that the resulting
drawing is c-planar?
Known polynomial subcases:
•
Maximum face-size at most 5 or
“single conflict”
graph
[Di Battista, Frati 09]
•
At most two components per cluster-induced graph
[Jelinek et al. 09]
•
Clustered cycles:
3 clusters
[Cortese et al. 05]
,
3 vertices/cluster
[Jelinkova at al. 09]
Flat & Embedded
Saturators
(Well known) idea:
Flat embedded clustered graphs
1.
Each node starts within its own cluster region.
2.
Merge cluster regions along edges within the same cluster.
Step 2 is rather trivial to do in polynomial time…
3
0
7
4
1
8
5
10
9
6
Y
Observe
No nodes of same cluster
are adjacent after Step 2.
2
X
Saturators
(Well known) idea:
Flat embedded clustered graphs
1.
Each node starts within its own cluster region.
2.
Merge cluster regions along edges within the same cluster.
3.
Merge cluster regions of same cluster by adding
connectivity-establishing edges
(
con-edges
)
Saturator
Step 2 is rather trivial to do in polynomial time…
…but how to choose the con-edges in
Step 3?
7
1
8
5
6
Y
2
X
Saturators
(Well known) idea:
Flat embedded clustered graphs
1.
Each node starts within its own cluster region.
2.
Merge cluster regions along edges within the same cluster.
3.
Merge cluster regions of same cluster by adding
connectivity-establishing edges (
con-edges
)
Saturator
Step 2 is rather trivial to do in polynomial time…
…but how to choose the con-edges in
Step 3?
7
1
8
5
6
Y
2
X
Aim
For each cluster, pick a
spanning tree from its
con-edges, s.t. the different
spanning trees do not cross.
Saturators
(Well known) idea:
Flat embedded clustered graphs
1.
Each node starts within its own cluster region.
2.
Merge cluster regions along edges within the same cluster.
3.
Merge cluster regions of same cluster by adding
connectivity-establishing edges (
con-edges
)
Saturator
Step 2 is rather trivial to do in polynomial time…
…but how to choose the con-edges in
Step 3?
7
1
8
5
6
Y
2
X
Aim
For each cluster, pick a
spanning tree from its
con-edges, s.t. the different
spanning trees do not cross.
Single-conflict graph
“Single conflict graph”
If every con-edge is involved in at most one crossing, the problem is
polynomial time solvable
[Di Battista, Frati 09]
So, this is not the case here…
7
1
8
5
6
Y
2
X
2 vertices per cluster on each face
Our restriction:
At most
two vertices per cluster on each face
.
(“Single-conflict” graphs are a subset of those graphs)
f
d
i
c
a
e
b
j
g
h
k
Not c-planar…
Here:
By simple deduction, this graph is not c-planar
f
d
i
c
a
e
b
j
g
h
k
Our algorithm
Automatically find a chain of deduction
arguments to answer the c-planarity
question.
Algorithm – Overview
Sequence of
4
Tests
(detect non-c-planarity) and
8
Simplifications
(shrink instance)
(1)
if
each remaining con-edge has at most one crossing
then
return
A
LGORITHM
F
OR
S
INGLE
C
ONFLICT
[Di Battista, Frati 09]
(2)
if
Test1
= true
then
return
“non-c-planar”
(3)
if
Simpl1
applicable
then
perform
Simpl1
&
goto
(1)
(4)
if
Test2
= true
then
return
“non-c-planar”
(5)
if
Simpl2
applicable
then
perform
Simpl2
&
goto
(1)
(6)
if
Simpl3
applicable
then
perform
Simpl3
&
goto
(1)
(7–12)
…
(13)
perform
Simpl8
&
goto
(1)
//always applicable of we got that far
Algorithm – Details
b
d
c
a
Let
A[
]
the multigraph of all con-edges for cluster
.
The first couple of tests & simplifications are trivial, e.g.
•
Test.
Disconnected
A[
]
No spanning tree
non-c-planar
•
Simplification.
Bridge in
A[
]
Merge vertices
Algorithm – Details
The next ones aren’t too hard either, e.g.
•
Test.
Cyclic crossing sequence of odd length.
r
R
o
g
O
G
The final ones are harder and more cumbersome – but interesting, e.g.
•
Simplifications 6–8.
“
-donut”
Simplification 6:
If
isomorphic
conflicting structures at two spokes
remove one of the spokes and pick the crossing edges
Algorithm – Details
Algorithm
Wrapping up
Eventually (after several applications of the various simplifications),
all
-donuts vanish.
No con-edges with multiple crossings anymore
Single-conflict graph
solvable in polynomial time.
Since each test and simplification requires only polynomial time:
Theorem.
The above algorithm decides c-planarity for
flat embedded
clustered graphs
with at most two vertices per cluster on each face
correctly in polynomial time.
Thank you
The road ahead…
What’s the problem with more vertices of the same cluster on a common
face?
The road ahead…
What’s the problem with more vertices of the same cluster on a common
face?
The road ahead…
What’s the problem with more vertices of the same cluster on a common
face?
The road ahead…
What’s the problem with more vertices of the same cluster on a common
face?
The road ahead…
What’s the problem with more vertices of the same cluster on a common
face?
Anyhow… is it possible to always deal with richer faces efficiently?
Thank you
This research work explores the complexity and special cases of C-planarity testing in embedded flat clustered graphs. It discusses the challenges, known polynomial subcases, and the concept of saturators in the context of flat embedded clustered graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Advances on Testing C-Planarity of Embedded Flat Clustered Graphs Markus Chimani (Osnabr ck University) Joint work with Guiseppe Di Battista (University Roma Tre) Fabrizio Frati (University of Sydney) Karsten Klein (Monash University)
Clustered Planarity (C-Planarity) 2 0 1 2 8 3 4 5 C = (G,T) 7 4 7 6 8 9 0 1 3 2 5 6 9 0 1 2 Complexity of c-planarity testing 3 4 c-connected: non c-connected: open for ~20 years O(|V|) [Dahlhaus 98] P? NP? 5 7 6 8 9 markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Complexity for special cases 3 Polynomial cases C-connected [Feng et al. 95], [Dahlhaus 98] Completely c-connected [Cornelsen, Wagner 06] Almost c-connected [Gutwenger et al. 02] Extrovert [Goodrich et al. 05] Cycles of Clusters [Cortese et al. 05] and many more Unfortunately, most cases are very restricted and/or unnatural Complexity even unknown for natural, seemingly simple subcases What if G is already embedded? What if the cluster hierarchie is flat, i.e, only one level of clusters? What if both? markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Flat & Embedded 4 Now: Flat embedded clustered graphs One level of clusters (= no nested clusters) G is embedded. Does there exist a drawing of the cluster regions such that the resulting drawing is c-planar? 0 1 2 3 4 5 7 6 8 9 Known polynomial subcases: Maximum face-size at most 5 or single conflict graph [Di Battista, Frati 09] At most two components per cluster-induced graph [Jelinek et al. 09] Clustered cycles: 3 clusters [Cortese et al. 05], 3 vertices/cluster [Jelinkova at al. 09] markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Saturators 5 (Well known) idea: Flat embedded clustered graphs 1. Each node starts within its own cluster region. 2. Merge cluster regions along edges within the same cluster. Step 2 is rather trivial to do in polynomial time 0 1 2 Y 3 Observe No nodes of same cluster are adjacent after Step 2. 4 5 6 7 10 8 9 X markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Saturators 6 (Well known) idea: Flat embedded clustered graphs 1. Each node starts within its own cluster region. 2. Merge cluster regions along edges within the same cluster. 3. Merge cluster regions of same cluster by adding connectivity-establishing edges (con-edges) Saturator Step 2 is rather trivial to do in polynomial time but how to choose the con-edges in Step 3? 1 2 Y 5 6 7 8 X markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Saturators 7 (Well known) idea: Flat embedded clustered graphs 1. Each node starts within its own cluster region. 2. Merge cluster regions along edges within the same cluster. 3. Merge cluster regions of same cluster by adding connectivity-establishing edges (con-edges) Saturator Step 2 is rather trivial to do in polynomial time but how to choose the con-edges in Step 3? 1 2 Y Aim For each cluster, pick a spanning tree from its con-edges, s.t. the different spanning trees do not cross. 5 6 7 8 X markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Saturators 8 (Well known) idea: Flat embedded clustered graphs 1. Each node starts within its own cluster region. 2. Merge cluster regions along edges within the same cluster. 3. Merge cluster regions of same cluster by adding connectivity-establishing edges (con-edges) Saturator Step 2 is rather trivial to do in polynomial time but how to choose the con-edges in Step 3? 1 2 Y Aim For each cluster, pick a spanning tree from its con-edges, s.t. the different spanning trees do not cross. 5 6 7 8 X markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Single-conflict graph 9 Single conflict graph If every con-edge is involved in at most one crossing, the problem is polynomial time solvable [Di Battista, Frati 09] 1 2 Y 5 6 7 8 X So, this is not the case here markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
2 vertices per cluster on each face 10 Our restriction: At most two vertices per cluster on each face. ( Single-conflict graphs are a subset of those graphs) g k b d l k a e h j c i f markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Not c-planar 11 Here: By simple deduction, this graph is not c-planar g k b d l k a e h j c Our algorithm Automatically find a chain of deduction arguments to answer the c-planarity question. i f markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Algorithm Overview 12 Sequence of 4 Tests (detect non-c-planarity) and 8 Simplifications (shrink instance) (1) if each remaining con-edge has at most one crossing then return ALGORITHMFORSINGLECONFLICT [Di Battista, Frati 09] if Test1 = true then return non-c-planar if Simpl1 applicable then perform Simpl1 & goto (1) if Test2 = true then return non-c-planar if Simpl2 applicable then perform Simpl2 & goto (1) if Simpl3 applicable then perform Simpl3 & goto (1) (7 12) (13) perform Simpl8 & goto (1) (2) (3) (4) (5) (6) //always applicable of we got that far markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Algorithm Details 13 Let A[ ] the multigraph of all con-edges for cluster . The first couple of tests & simplifications are trivial, e.g. Test. Disconnected A[ ] No spanning tree non-c-planar a c d b Simplification. Bridge in A[ ] Merge vertices g g b b a e a e c d cd f f markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Algorithm Details 14 The next ones aren t too hard either, e.g. Test. Cyclic crossing sequence of odd length. r G o g O R markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Algorithm Details 15 The final ones are harder and more cumbersome but interesting, e.g. Simplifications 6 8. -donut spokes Simplification 6: If isomorphic conflicting structures at two spokes remove one of the spokes and pick the crossing edges markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
Algorithm 16 Wrapping up Eventually (after several applications of the various simplifications), all -donuts vanish. No con-edges with multiple crossings anymore Single-conflict graph solvable in polynomial time. Since each test and simplification requires only polynomial time: Theorem. The above algorithm decides c-planarity for flat embedded clustered graphs with at most two vertices per cluster on each face correctly in polynomial time. Thank you markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
The road ahead 17 What s the problem with more vertices of the same cluster on a common face? markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
The road ahead 18 What s the problem with more vertices of the same cluster on a common face? markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
The road ahead 19 What s the problem with more vertices of the same cluster on a common face? markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
The road ahead 20 What s the problem with more vertices of the same cluster on a common face? markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
The road ahead 21 What s the problem with more vertices of the same cluster on a common face? Anyhow is it possible to always deal with richer faces efficiently? Thank you markus . chimani @ uni - osnabrueck . de C-Planarity @ Flat Embedded Graph Drawing 2014
