Transcript Given any resolution rule, a planar straight line upward drawing of

Proving Lower Bounds on Graph
Drawing Problems
Rajat Anantharam
Department of Gaming and Media Technology
Utrecht University
Objective


Technique for proving exponential area lower
bounds
The Logic Engine




Description
Illustration
Simulation
Extension
Tune ups

Planar acyclic graphs

Exponential variables

Planar straight line Upward drawing

Upper and Lower bounds
Digraphs G1 and Gn
Tn
t1
Tn-1
Tn-2
t0
Gn
Gn-1
G1
s0
Sn-2
s1
(a)
Sn-1
Sn
(b)
Theorem 1
Given any resolution rule, a planar straight
line upward drawing of digraph Gn (with 2n +
2 vertices) has area p(2n)
Approach to Proving
With An as the minimum area of a planar straight line
upward drawing Gn We use induction to prove that
An >= 4. An -2
Since A1 >= c for some constant c depending on the
resolution rule, this implies the claimed result.
Variable Instantiation



Gn  straight line drawing of Gn with min area
Gn-1  straight line drawing of Gn-1 by removing
vertices and edges sn and tn
Gn-2 for Gn-2 and so on ..
Variable Instantiation – Part 2
s  Horizontal line through vertex sn-2
t  Horizontal line through vertices tn-2
r1  Line extending edge (tn-3, tn-2)
q1  Angle formed by edge (tn-3, tn-2) and the x-axis
q2  Angle fomed by edge (sn-2, sn-3) and the x-axis
l1  Line paralle to r1 through vertex sn-2
l2  Line extending edge (sn-2, sn-3)
Observations Leading to
Inference
Area(P) >= 2 * Area(Gn-2) >= 2 * An-2
An = Area(Gn) >= Area(P) + Area(D1) + Area(D2)
An = 2 * Area(P) >= 4 * Area(Gn-2) = 4 * An-2
Logic Engine
Links in a Chain
Each armature is connected to the
shaft by a chain
When the engine lies flat then the
chain can be in two possible
positions – viz.aj and aj*
If xj = 1, aj = xj
If xj = 0, aj* = xj
For clauses c1, c2, ... cm the chain
links are numbered in outward
order as 1,2, ... m
Flags and Flag Collision

The Flag



Two flags attached along the same row
across two armatures collide with each
other if they point towards each other
Flag connected to the outermost armature
An collides with the frame if it points
towards it
If literal xj appears in the clause ci then link
i of aj is unflagged
If the literal xj * appears in the clause ci
then the link i of aj * is unflagged
Theorem
An instance of NAE3SAT is a “yes” instance if and
only if the corresponding logic engine has a flat
collission free configuration.
And .. The proof





Assume “yes” instance of NAE3SAT
Rotate armatures such that if truth assignment t(xj) = 1, aj is on top
and if t(xj) = 0, aj is in bottom
Since clause ci contains atleast one literal y with t(y) = 1 and atleast
one literal z with t(z) = 0 there’s atleast one unflagged link in each row.
So we allign the chain such that the flaggs from the remaining link
point towards the unflagged link leading to “no collission”
A similar analogy can be drawn from a flat collission free configuration
thereby implying the validity of the theorem
Logic engine and a graph
Drawing Problem
To prove that the following problem is NP-Hard
Theorem :
“Unit length planar straight line drawing of a graph is NPHard”
The question: - Is there a straight line planar drawing of G
such that every edge is of length one ?
Prelude


How to construct the unversal part of a logic graph?
A graph G is uniquely drawable if all the unit length
planar drawings f G can be obtained through
translation, rotation, scaling, mirroring
Construction of the Logic
Engine



Each unit length of the
constructed Logic Engine
corresponds to the link graph
Armature and Outer frame is
necessarily unique
The max Euclidean distance b/w
the extremal endpoints to the
shaft gives the number of edges
in the shaft making its
construction unique as well
Hence the Proof
The logic graph corresponding to an instance of
NAE3SAT with n variables and m clauses has
O((m+n)2) vertices and edges and the time taken to
construct the logical graph is linear in the size of the
graph
Extending Usage of Logic
Graphs




Is there a grid drawing of a tree T, such that each edge has
length one ?
Is there a grid drawing of tree T of area at most K ? – where K
is an integer.
Is there a drawing of tree T such that T is a minimum spanning
tree of the vertex locations?
Is there a drawing of graph G such that G is the mutual nearest
neighbour graph of the vertex location?
Thank You