Embeddings of graphs on arrangements of planes in three dimensions

Summary

The mathematics of embeddings of graphs in three dimensions, concentrating on sets of parallel planes.

Supervisor(s)

Professor Peter Eades

Research Location

Information Technologies

Program Type

N/A

Synopsis

An arrangement of planes is the union of 2-dimensional linear subspaces of R3. Two planes may share a line, and three planes may share a point; in some case, more than 3 planes may share a point. Suppose that A is an arrangement of k planes in three R3, and G is a finite graph. We want to embed G on A: every vertex of G is on at least one plane of A; every edge of G is a curve that wholly lies on one plane of A; no pair of such curves are allowed to cross. Such an embedding is called a multiplane embedding on A. This project aims to study multiplane embeddings from the both mathematical and computational points of view. We need to establish elegant (mathematical) criteria for the existence of multiplane embeddings (especially when the number of planes is small), and to determine the complexity of computing such embeddings.

Keywords

Discrete mathematics, geometry, graph, topology, algorithms

Opportunity ID

The opportunity ID for this research opportunity is: 398

Other opportunities with Professor Peter Eades

• Visual Analytics
• Geometric Algorithms
• Algorithmics for social networks
• Embedding graphs in non-Euclidean geometries
• Drawing Algorithms for Almost Planar Graphs