Paper Info
Title
On the obfuscation complexity of planar graphs
Abstract
Being motivated by John Tantalo’s Planarity Game, we consider straight line plane drawings of a planar graph G with edge crossings and wonder how obfuscated such drawings can be. We define obf(G), the obfuscation complexity of G, to be the maximum number of edge crossings in a drawing of G. Relating obf(G) to the distribution of vertex degrees in G, we show an efficient way of constructing a drawing of G with at least obf(G)/3 edge crossings. We prove bounds (δ(G)2/24−o(1))n2≤obf(G)<3n2 for an n-vertex planar graph G with minimum vertex degree δ(G)≥2.
Year
DOI
Venue
2008
10.1016/j.tcs.2008.02.032
Theoretical Computer Science
Keywords
DocType
Volume
Combinatorial games,Planar graphs,Straight line drawings,Computational complexity
Journal
396
Issue
ISSN
Citations 
1
0304-3975
9
PageRank 
References 
Authors
0.97
7
1
Name
Order
Citations
PageRank
Oleg Verbitsky119127.50