Barycentric systems and stretchability |
| |
Authors: | Hubert de Fraysseix |
| |
Institution: | Centre d’Analyse et de Mathématique Sociales, CNRS UMR 8557, École des Hautes Études en Sciences Sociales, 54 Boulevard Raspail, 75006 Paris, France |
| |
Abstract: | Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least three free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible. |
| |
Keywords: | 05C10 57M15 |
本文献已被 ScienceDirect 等数据库收录! |
|