Universal point sets for planar three-trees |
| |
Institution: | 1. Department of Industrial Engineering and Operations Research, Columbia University, New York City, NY, USA;2. Department of Mathematics, California State University Northridge, Los Angeles, CA, USA;3. Department of Computer Science, Tufts University, Medford, MA, USA |
| |
Abstract: | For every , we present a set of points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of . This is the first subquadratic upper bound on the cardinality of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs. |
| |
Keywords: | Planar three-tree Universal point set Graph embedding |
本文献已被 ScienceDirect 等数据库收录! |
|