Open AccessTreetopes and their Graphs
Author(s) -
David Eppstein
Publication year - 2015
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1137/1.9781611974331.ch69
Subject(s) - polytope , planarity testing , polyhedron , combinatorics , generalization , base (topology) , facet (psychology) , characterization (materials science) , mathematics , pathwidth , chordal graph , graph , face (sociological concept) , discrete mathematics , computer science , line graph , psychology , social psychology , materials science , personality , sociology , big five personality traits , nanotechnology , social science , mathematical analysis
We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base facet such that every face of dimension greater than one intersects the base in more than one point. We prove an equivalent characterization of the 4-treetopes using the concept of clustered planarity from graph drawing, and we use this characterization to recognize the graphs of 4-treetopes in polynomial time. This result provides one of the first classes of 4-polytopes, other than pyramids and stacked polytopes, that can be recognized efficiently from their graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom