Melvin's digital garden

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

  1. find a good embedding
  2. 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

Links to this note