Universal point sets for planar three-trees期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

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 $n \in N$ , we present a set $S_{n}$ of $O (n^{3 / 2} \log ? n)$ 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 $S_{n}$ . 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 等数据库收录！