(Luca Castelli Aleardi, Ecole Polytechnique, presented at the *27th. Int. Symp. on Graph Drawing 2019*)

In this work we consider balanced Schnyder woods for planar graphs, which are Schnyder woods where the number of incoming edges of each color at each vertex is balanced as much as possible. We provide a simple linear-time heuristic allowing us to obtain well balanced Schnyder woods in practice. As test applications we consider two important algorithmic problems: the computation of Schnyder drawings and the computation of small cycle separators.

While not being able to provide theoretical guarantees, our experimental results (on a wide collection of planar graphs) suggest that the use of balanced Schnyder woods leads to an improvement of the quality of the layout of Schnyder drawings, and provides an efficient tool for computing short and balanced cycle separators.

- SchnyderLayoutComputation.jar (compiled with Java 1.8): a runnable .jar file for the computation of Schnyder drawings (with 3D rendering)
- SchnyderShortSeparatorComputation.jar (compiled with Java 1.8): a runnable .jar file for the computation of balanced Schnyder woods and short simple cycle separators (with 3D rendering)
- FastSchnyderComputation.jar (compiled with Java 1.8): a fast implementation of all algorithms, for performing benchs and evaluating the runtime performances of all algorithms involving Schnyder woods

java -jar SchnyderLayoutComputation.jar sphere12k.off 100(3D rendering available only for meshes with up to 300000 vertices)

java -jar SchnyderShortSeparatorComputation.jar sphere12k.off 100(3D rendering available only for meshes with up to 300000 vertices)

java -Xms4G -Xmx4G -jar FastSchnyderComputation.jar horse1.off(for computing statistics and runtime performances: tests are repeated with 100 initial random seeds)

Schnyder drawing computation (Ecole Polytechnique, 2019) Reading a collection of polygonal faces from OFF format (shared vertex representation): /home/amturing/Desktop/doc/datasets/OFF/Synthetic/sphere12k.off Reading vertices...done 12962 vertices Reading face degrees...done 25920 faces Triangle soup loaded from from OFF file (0.909854272 seconds) Building a (pointer based) halfedge representation of a surface mesh...done (0.063991961 seconds) Checking Polyhedron...ok Closed mesh: no boundaries The mesh is pure triangle n: 12962 e: 38880 f: 25920 b:0 genus: 0 Checking Polyhedron...ok Closed mesh: no boundaries The mesh is pure triangle n: 12962 e: 38880 f: 25920 b:0 genus: 0 Initialize Schnyder wood computation: root face (v3932, v4355, v8252) root edge e100 (v3932, v4355) Schnyder wood computed Schnyder drawing initialization...done (memory usage: 47 MBytes) Computing the size of subtrees in T0...done Computing the height of nodes in the tree T0...done Computing the height of nodes in the tree T1...done Computing the height of nodes in the tree T2...done max length=1.4142135623730951, avg length=0.01871947752984827, edge length aesthetic=0.9912204024607774 f= 25919.0 n= 12962

Fast computation of Schnyder woods and simple cycle separators (Ecole Polytechnique, 2019) Reading a collection of polygonal faces from OFF format (shared vertex representation): /home/amturing/Desktop/doc/datasets/OFF/LargePlanarTri/horse1.off Reading vertices...done 20000 vertices Reading face degrees...done 39996 faces Triangle soup loaded from from OFF file (1.074451719 seconds) Building a (pointer based) halfedge representation of a surface mesh...done (0.0845149 seconds) Checking Polyhedron...ok Closed mesh: no boundaries The mesh is pure triangle n: 20000 e: 59994 f: 39996 b:0 genus: 0 Creating an array based half edge DS from a Polyhedron...done (0.029173073 s, 19 MBytes) Running warming phase...done Running runtime benchmarks --- Starting test 1 --- Running garbage collector...done Schnyder wood initialization: root face (v5348, v5347, v10420) root edge e6144 (v5348, v5347) Fast computation of a balanced Schnyder wood...done (0.005126275 seconds) Schnyder drawing initialization...done (memory usage: 20 MBytes) Fast computation of the Schnyder drawing...done (0.00669152 seconds) Computing shortest balanced separator...done (3.87792E-4 seconds) Separator statistics: best vertex: v16361 sqrt(8.0m)=692 sqrt(8.0n)=400, sqrt(m)=244, sqrt(n)=141 boundary size: 173 normalized boundary size: 0.706 sqrt(m) normalized boundary size: 0.432 sqrt(8n) separator balance: 6737 (0.336 n) --- end of test 1 --- .......... .......... .......... .......... --- Starting test 100 --- Running garbage collector...done Schnyder wood initialization: root face (v718, v720, v16136) root edge e735 (v718, v720) Fast computation of a balanced Schnyder wood...done (0.00483866 seconds) Schnyder drawing initialization...done (memory usage: 20 MBytes) Fast computation of the Schnyder drawing...done (0.01222462 seconds) Computing shortest balanced separator...done (3.59825E-4 seconds) Separator statistics: best vertex: v3179 sqrt(8.0m)=692 sqrt(8.0n)=400, sqrt(m)=244, sqrt(n)=141 boundary size: 159 normalized boundary size: 0.649 sqrt(m) normalized boundary size: 0.397 sqrt(8n) separator balance: 9492 (0.474 n) --- end of test 100 --- --- Runtime time performances (results expressed in seconds) --- Number of tests: 100 minimum=0.0108 maximum=0.0286 median=0.0123 |