Skip to content

Take in a graph made up of vertices and edges, which may not be planar, and add vertices at intersection points of edges to reinstate planarity

Notifications You must be signed in to change notification settings

ammanvedi/to-planar-graph

Repository files navigation

To Planar Graph

This library aims to solve the following problem;

Given a graph embedded in a 2d coordinate space, and the embedding is not planar, make changes to the graph such that after the changes the graph is planar. The Changes that will be made conform to the following

  1. Do not change the position of any of the vertices.
  2. Do not change the positions or directions of any of the edges.

The changes may;

  1. Add new vertices at intersection points of edges.
  2. Re route edges that cross over vertices.

Installation

npm install --save to-planar-graph

Usage

import { toPlanarGraph } from "to-planar-graph";

/**
 * Nodes are defined as a coordinate position. Their "id" used
 * in edges is their index in the input
 * 
 * You can see more examples in the tests.
 */
const nodes: Array<[number, number]> = [
    [10, 10],
    [70, 50],
    [80, 70],
    ...
]

/**
 * Edges are defined by [source id, target id]
 */
const edges: Array<[number, number]> = [
    [0, 1],
    [1, 3],
    [1, 2],
    ...
]

const threshold = 5;

const result = toPlanarGraph(nodes, edges, threshold)

About the "Threshold"

Consider the following graph as input

The graph is clearly not planar. We could say this because of one of two reasons

  1. The edge B->E intersects the edge A->C
  2. The edge B->E intersects the vertex C

Now in the first scenario we would create a new vertex F, and then create the path B->F->E and A->F->C

But this may not be very good when we display our graph visually, even if logically it may be correct. We would end up with a graph where a vertex overlaps another.

To avoid this we can check each intersection for its proximity to a vertex, this is what the threshold describes. If a vertex is found within threshold the new edges will be routed through the edge that is within the threshold distance.

It is suggested that the size of this threshold is the radius of the display size of the vertices in your coordinate system. For example if you show your vertices as 10 pixel squares a sensible threshold may be 5 (pixels).

Acknowledgements

The intersections are performed using the Bentley-Ottmann algorithm from the isect library, its very cool and fast too

I built this library for use alongside planar-face-discovery

About

Take in a graph made up of vertices and edges, which may not be planar, and add vertices at intersection points of edges to reinstate planarity

Resources

Stars

Watchers

Forks

Packages

No packages published