Turan type problems
Presented by Peter Eades, Australia, New Castle at AAAC 2011
Investigation of turan type problem lead to better network visualization.
Graph: vertices and edges Topological embedding: G + edge crossing, faces, ordered incidence Graph drawing: location of vertices, route for each edge
- find a good embedding
- find a good drawing
properties of good drawings, validated by human exps
turan-type problem: forbidden substructure, what is the maximal substructure that does not contain a forbidden substructure e.g. what is the most number of edges for a graph with n vertices that is planar?
algorithmic problem: determine whether a given structure is free of the forbidden substructure
In many classes of graph drawings, no algorithms for checking.
Right angle crossing (RAC): straight lines, all edge crossing at 90 degree
RAC graph has at most 4n-10 edges
- crossing graph is bipartite
- red, blue, green edges
- circle packing, primal dual graph is a RAC graph with 4n-10 edges