Dear colleagues, in the graph theory the question of convex graph representation is widely discussed. However till now i haven't manage to find any practical reasoning and justification for these studies. As i currently work on the topic of convex representation of planar graphs and want to write sort overview, i would very appreciate any hints/ideas/literature references about practical justification of studying convex (planar) graph representation.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Although what constitutes a "practical justification" is in the eye of the beholder, I would think this might qualify.
There is a notion called geometric routing that is used to solve network routing problems. The idea is to map the true GPS coordinates of a planar network on to a differently embedded network that supports fast and efficient routing. One such is greedy routing, which as its name implies, is an especially simple algorithm. There has been a conjecture that there exists a convex embedding which supports greedy routing. This has been proved, but only by losing another nice property, "succintness" (bits per vertex coordinate). Others have retained succinctness by changing the metric and using a convex embedding.
These complex details aside, the point is that convex embeddings of planar graphs are used as a basis for network routing algorithms. You could start with this paper, published just a month ago or so, and trace through its references:
He, Zhang. "A simple routing algorithm based on Schnyder coordinates." Theoretical Computer Science. February 2013. (Elsevier link)
answered Apr 12, 2013 at 0:03