← All problems

Linear-Volume 3D Grid Drawings of Planar Graphs

For every planar graph GG on nn vertices, determine whether there is an injective placement of its vertices at points of a three-dimensional integer grid such that straight edges do not cross and the bounding-box volume is O(n)O(n).

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li