Counting Carambolas

Adrian Dumitrescu; Maarten Löffler; André Schulz; Csaba Tóth

doi:10.1007/s00373-015-1621-7

Counting Carambolas

Adrian Dumitrescu, Maarten Löffler, André Schulz, Csaba Tóth^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of n points in the plane. Configurations of interest include convex polygons, star-shaped polygons and monotone paths. We also consider related problems for directed planar straight-line graphs.

Original language	English
Pages (from-to)	923-942
Journal	Graphs and Combinatorics
Volume	32
Issue number	3
Early online date	2015
DOIs	https://doi.org/10.1007/s00373-015-1621-7
Publication status	Published - 2015

Keywords

CG, GRAPH

Access to Document

10.1007/s00373-015-1621-7

s00373-015-1621-7Final published version, 841 KBLicence: Taverne

Cite this

@article{c2dbb8a57c374587b7c37c115cd7e52b,

title = "Counting Carambolas",

abstract = "We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of n points in the plane. Configurations of interest include convex polygons, star-shaped polygons and monotone paths. We also consider related problems for directed planar straight-line graphs.",

keywords = "CG, GRAPH",

author = "Adrian Dumitrescu and Maarten L{\"o}ffler and Andr{\'e} Schulz and Csaba T{\'o}th",

year = "2015",

doi = "10.1007/s00373-015-1621-7",

language = "English",

volume = "32",

pages = "923--942",

journal = "Graphs and Combinatorics",

issn = "1435-5914",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Counting Carambolas

AU - Dumitrescu, Adrian

AU - Löffler, Maarten

AU - Schulz, André

AU - Tóth, Csaba

PY - 2015

Y1 - 2015

N2 - We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of n points in the plane. Configurations of interest include convex polygons, star-shaped polygons and monotone paths. We also consider related problems for directed planar straight-line graphs.

AB - We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of n points in the plane. Configurations of interest include convex polygons, star-shaped polygons and monotone paths. We also consider related problems for directed planar straight-line graphs.

KW - CG, GRAPH

U2 - 10.1007/s00373-015-1621-7

DO - 10.1007/s00373-015-1621-7

M3 - Article

SN - 1435-5914

VL - 32

SP - 923

EP - 942

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Counting Carambolas

Abstract

Keywords

Access to Document

Fingerprint

Cite this