Drawing Planar Graphs with Few Geometric Primitives:
Algorithms and Evaluation

Philipp Kindermann Wouter Meulemans André Schulz
http://tutte.fernuni-hagen.de/userstudy
http://tutte.fernuni-hagen.de/web/userstudy/talk-extended

Visual Complexity

Number of geometric objects
Edges: 21
Segments: 21
Why?
1. Aesthetic
2. Path Finding

Known Results - Segments

Class Segments Grid
Lower Upper Segm. Area
tree ϑ/2 [1] ϑ/2 [1]
max. outerp. n [1] n [1]
2-trees 3n/2 [1] 3n/2 [1]
3-trees 2n [1] 2n [1]
2-connected 2n [1] 8n/3 [2]
3-connected 2n [1] 5n/2 [1]
cubic 3-conn. n/2 [3] n/2 [4] n/2 [4] O(n)×O(n)
triangulation 2n [2] 7n/3 [2]
planar 2n [2] 8n/3 [2]
[1] Dujmović et al. 2007
[2] Durocher & Mondal 2014
[3] Mondal et al. 2013
[4] Igamberdiev et al. 2015

Tree Drawing

Theorem: Trees, 3n/4 segments, O(n2)×O(n1.58) grid
heavy path decomposition
  • draw each heavy path tree in a box
  • boxes of same level are disjoint

level 0:
level k:
one vertex:
Theorem: Trees, ϑ/2 segments, quasipol. grid

Results - Segments

Class Segments Grid
Lower Upper Segm. Area
tree ϑ/2 [1] ϑ/2 [1] 3n/4 O(n2)×O(n1.58)
ϑ/2 quasipol.
max. outerp. n [1] n [1]
2-trees 3n/2 [1] 3n/2 [1]
3-trees 2n [1] 2n [1]
2-connected 2n [1] 8n/3 [2]
3-connected 2n [1] 5n/2 [1]
cubic 3-conn. n/2 [3] n/2 [4] n/2 [4] O(n)×O(n)
triangulation 2n [2] 7n/3 [2]
planar 2n [2] 8n/3 [2]

Planar 3-Trees

1 2 3 4 5 6 7 8
canonical order
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
Schnyder realizer
Bonichon et al. [ICALP'02]:
A min. Schnyder realizer has at most 2n - 5 leaves in total.

⇒ Red tree has at most (2n − 5) / 3 segments
⇒ Blue tree has at most n - 3 segments
⇒ Green tree has at most n - 3 segments
⇒ Drawing has at most (8n - 22) / 3 segments

Width: n - 1
Height: ≤ (2n - 5) / 3 ⋅ (n - 1)

Theorem: Planar 3-tree, (8n - 22) / 3 segments, O(n) × O(n2) grid

Results - Segments

Class Segments Grid
Lower Upper Segm. Area
tree ϑ/2 [1] ϑ/2 [1] 3n/4 O(n2)×O(n1.58)
ϑ/2 quasipol.
max. outerp. n [1] n [1] 3n/2 O(n)×O(n2)
2-trees 3n/2 [1] 3n/2 [1] 17n/6 O(n)×O(n2)
3-trees 2n [1] 2n [1] 8n/3 O(n)×O(n2)
2-connected 2n [1] 8n/3 [2] 17n/6 O(n)×O(n2)
3-connected 2n [1] 5n/2 [1] 8n/3 O(n)×O(n2)
cubic 3-conn. n/2 [3] n/2 [4] n/2 [4] O(n)×O(n)
triangulation 2n [2] 7n/3 [2] 8n/3 O(n)×O(n2)
planar 2n [2] 8n/3 [2] 17n/6 O(n)×O(n2)

Tree Algorithms

Tidier
[Reingold & Tilford '81], [Walker II '90]
Quad
[Rusu et al. '08]
FewSeg
[WG '17]
Parallel levels Parent centered
Specified angular resolution Evenly spread out children
Heavy path decomposition
Min. number of segments
Heuristic area reduction

Sparse Graphs Algorithms

ForceDirected
[Fruchterman & Reingold '81]
 Well separated vertices Adjacent vertices close
ForceDirFewSeg

Like ForceDirected... But we can straighten paths

Task: Aesthetics

Task: Path Finding

Task: Furthest Pair

Hypotheses

ForceDirected
ForceDirFewSeg
H1: Path Finding
ForceDirFewSeg > ForceDirected
H2: Aesthetics
ForceDirected > ForceDirFewSeg
H3: Furthest Pair
FewSeg > Tidier > Quad
H4: Aesthetics
Math/CS:
Other:
Tidier > FewSeg > Quad
FewSeg > Tidier > Quad
Tidier
Quad
FewSeg

Stimuli

Sparse Graphs Trees
Layout ForceDirected ForceDirFewSeg Tidier Quad FewSeg
Type ROME Random Balanced Deep Wide
Size 20 nodes 40 nodes 20 nodes 40 nodes
Task Shortest Path Aesthetics Furthest Pair Aesthetics
Rep. 2 Rep. 4 Rep. 2 Rep. 4 Rep.
Tasks
Users 42 21 21
92 tasks in total: split into three groups
84 users: distribute evenly among groups

Results

H1: Path Finding
ForceDirFewSeg > ForceDirected
50% 25% 0% Error Rate - 656 responses
ForceDirFewSeg
ForceDirected
20s 10s 0s Response Time - 656 responses

Results

H2: Aesthetics
ForceDirected > ForceDirFewSeg
1 0.5 0 Preference - 656 responses
ForceDirFewSeg
ForceDirected

Results

H3: Furthest Pair
FewSeg > Tidier > Quad
50% 25% 0% Error Rate - 756 responses
FewSeg
Tidier
Quad
= :p > 0.05
≤ :p < 0.05
< :p < 0.01
≪ :p < 0.001
20s 10s 0s Response Time - 756 responses

Results

H4: Aesthetics
Math/CS:
Other:
Tidier > FewSeg > Quad
FewSeg > Tidier > Quad
1 0.5 0 Preference - 504 responses
FewSeg
Tidier
Quad
Follow-up study:
576 extra responses

Conclusion

ForceDirected
ForceDirFewSeg
H1: Path Finding
ForceDirected > ForceDirFewSeg
(except random large)
H2: Aesthetics
ForceDirected ≥ ForceDirFewSeg
H3: Furthest Pair
Tidier ≥ FewSeg > Quad
H4: Aesthetics
Math/CS:
Other:
Tidier > FewSeg > Quad
FewSeg > Tidier > Quad
Tidier
Quad
FewSeg