Straight Line Embedding

Graphs can be used to represent relational information. This is the reason why it is often useful to draw graphs in order to visualize this relational information.

Example Straight Line Embedding

A straight line embedding of a planar graph is a drawing such that all edges are drawn as straight lines. The resulting drawing is planar, i.e., edges do not cross, and all nodes have integer coordinates. Straight line embeddings are mainly important from a theoretical point of view. Interesting Fact: There is a straight line embedding for every planar graph G=(V,E) (without selfloops and parallel edges). The layout size is at most O(|V|)xO(|V|).

LEDA Functions for Straight Line Embedding

STRAIGHT_LINE_EMBED_MAP(): Let G=(V,E) be a planar graph without self loops and parallel edges representing a planar map. STRAIGHT_LINE_EMBED_MAP() computes a planar embedding of G in time O(|V|²). The x- and y-coordinates of the nodes are in the range [0,2-n2].

STRAIGHTLINE_EMBEDDING(): Let G=(V,E) be a planar graph without self loops and parallel edges. STRAIGHTLINE_EMBEDDING() computes a planar embedding of G in time O(|V|²). The only difference between STRAIGHTLINE_EMBEDDING() and STRAIGHT_LINE_EMBED_MAP() is that here a planar map of G is computed internally.

Example STRAIGHT_LINE_EMBEDDING()

Tip

Use Straight Line Embeddings to check whether a given graph is planar. Use one of the other algorithms if you want to visualize the structure of the graph.

See also:

Graph Drawing Algorithms

Algorithms for Planar Graphs

Planar Maps

Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Graph Drawing Algorithms