{"data":{"id":"10.48550/arxiv.math/0302126","type":"dois","attributes":{"doi":"10.48550/arxiv.math/0302126","prefix":"10.48550","suffix":"arxiv.math/0302126","identifiers":[{"identifier":"math/0302126","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"math/0302126"}],"creators":[{"name":"Orden, David","nameType":"Personal","givenName":"David","familyName":"Orden","affiliation":[],"nameIdentifiers":[]},{"name":"Santos, Francisco","nameType":"Personal","givenName":"Francisco","familyName":"Santos","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"The polytope of non-crossing graphs on a planar point set"}],"publisher":"arXiv","container":{},"publicationYear":2003,"subjects":[{"lang":"en","subject":"Combinatorics (math.CO)","subjectScheme":"arXiv"},{"lang":"en","subject":"Metric Geometry (math.MG)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"05C10 (primary), 52C25 (secondary)","subjectScheme":"MSC"}],"contributors":[],"dates":[{"date":"2003-02-11T19:08:02Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2009-11-30T18:10:20Z","dateType":"Updated","dateInformation":"v1"},{"date":"2003-02-12T18:02:24Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2009-11-30T18:10:20Z","dateType":"Updated","dateInformation":"v2"},{"date":"2003-05-30T10:53:12Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2009-11-30T18:10:20Z","dateType":"Updated","dateInformation":"v3"},{"date":"2003-02","dateType":"Available","dateInformation":"v1"},{"date":"2003","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1007/s00454-004-1143-1","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"For any finite set $\\A$ of $n$ points in $\\R^2$, we define a $(3n-3)$-dimensional simple polyhedron whose face poset is isomorphic to the poset of ``non-crossing marked graphs'' with vertex set $\\A$, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on $\\A$ appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension $2n_i +n -3$ where $n_i$ is the number of points of $\\A$ in the interior of $\\conv(\\A)$. The vertices of this polytope are all the pseudo-triangulations of $\\A$, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.","descriptionType":"Abstract"},{"description":"28 pages, 16 figures. Main change from v1 and v2: Introduction has been reshaped","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5NQVRILzAzMDIxMjY8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij5tYXRoLzAzMDIxMjY8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+T3JkZW4sIERhdmlkPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5EYXZpZDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5PcmRlbjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5TYW50b3MsIEZyYW5jaXNjbzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RnJhbmNpc2NvPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlNhbnRvczwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+VGhlIHBvbHl0b3BlIG9mIG5vbi1jcm9zc2luZyBncmFwaHMgb24gYSBwbGFuYXIgcG9pbnQgc2V0PC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDAzPC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+Q29tYmluYXRvcmljcyAobWF0aC5DTyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NZXRyaWMgR2VvbWV0cnkgKG1hdGguTUcpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogTWF0aGVtYXRpY3M8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9Ik1TQyI+MDVDMTAgKHByaW1hcnkpLCA1MkMyNSAoc2Vjb25kYXJ5KTwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDMtMDItMTFUMTk6MDg6MDJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDktMTEtMzBUMTg6MTA6MjBaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwMy0wMi0xMlQxODowMjoyNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwOS0xMS0zMFQxODoxMDoyMFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDAzLTA1LTMwVDEwOjUzOjEyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDA5LTExLTMwVDE4OjEwOjIwWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDMtMDI8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4xMDA3L3MwMDQ1NC0wMDQtMTE0My0xPC9yZWxhdGVkSWRlbnRpZmllcj4KICA8L3JlbGF0ZWRJZGVudGlmaWVycz4KICA8dmVyc2lvbj4zPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9hcnhpdi5vcmcvbGljZW5zZXMvYXNzdW1lZC0xOTkxLTIwMDMvIj5Bc3N1bWVkIGFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZSB0byBkaXN0cmlidXRlIHRoaXMgYXJ0aWNsZSBmb3Igc3VibWlzc2lvbnMgbWFkZSBiZWZvcmUgSmFudWFyeSAyMDA0PC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+Rm9yIGFueSBmaW5pdGUgc2V0ICRcQSQgb2YgJG4kIHBvaW50cyBpbiAkXFJeMiQsIHdlIGRlZmluZSBhICQoM24tMykkLWRpbWVuc2lvbmFsIHNpbXBsZSBwb2x5aGVkcm9uIHdob3NlIGZhY2UgcG9zZXQgaXMgaXNvbW9ycGhpYyB0byB0aGUgcG9zZXQgb2YgYGBub24tY3Jvc3NpbmcgbWFya2VkIGdyYXBocycnIHdpdGggdmVydGV4IHNldCAkXEEkLCB3aGVyZSBhIG1hcmtlZCBncmFwaCBpcyBkZWZpbmVkIGFzIGEgZ2VvbWV0cmljIGdyYXBoIHRvZ2V0aGVyIHdpdGggYSBzdWJzZXQgb2YgaXRzIHZlcnRpY2VzLiBUaGUgcG9zZXQgb2Ygbm9uLWNyb3NzaW5nIGdyYXBocyBvbiAkXEEkIGFwcGVhcnMgYXMgdGhlIGNvbXBsZW1lbnQgb2YgdGhlIHN0YXIgb2YgYSBmYWNlIGluIHRoYXQgcG9seWhlZHJvbi4KICBUaGUgcG9seWhlZHJvbiBoYXMgYSB1bmlxdWUgbWF4aW1hbCBib3VuZGVkIGZhY2UsIG9mIGRpbWVuc2lvbiAkMm5faSArbiAtMyQgd2hlcmUgJG5faSQgaXMgdGhlIG51bWJlciBvZiBwb2ludHMgb2YgJFxBJCBpbiB0aGUgaW50ZXJpb3Igb2YgJFxjb252KFxBKSQuIFRoZSB2ZXJ0aWNlcyBvZiB0aGlzIHBvbHl0b3BlIGFyZSBhbGwgdGhlIHBzZXVkby10cmlhbmd1bGF0aW9ucyBvZiAkXEEkLCBhbmQgdGhlIGVkZ2VzIGFyZSBmbGlwcyBvZiB0d28gdHlwZXM6IHRoZSB0cmFkaXRpb25hbCBkaWFnb25hbCBmbGlwcyAoaW4gcHNldWRvLXRyaWFuZ3VsYXRpb25zKSBhbmQgdGhlIHJlbW92YWwgb3IgaW5zZXJ0aW9uIG9mIGEgc2luZ2xlIGVkZ2UuCiAgQXMgYSBieS1wcm9kdWN0IG9mIG91ciBjb25zdHJ1Y3Rpb24gd2UgcHJvdmUgdGhhdCBhbGwgcHNldWRvLXRyaWFuZ3VsYXRpb25zIGFyZSBpbmZpbml0ZXNpbWFsbHkgcmlnaWQgZ3JhcGhzLjwvZGVzY3JpcHRpb24+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJPdGhlciI+MjggcGFnZXMsIDE2IGZpZ3VyZXMuIE1haW4gY2hhbmdlIGZyb20gdjEgYW5kIHYyOiBJbnRyb2R1Y3Rpb24gaGFzIGJlZW4gcmVzaGFwZWQ8L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/math/0302126","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-18T19:12:38.000Z","registered":"2022-03-18T19:12:39.000Z","published":"2003","updated":"2022-03-18T19:12:39.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.math/0302126","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}