---
_id: '13165'
abstract:
- lang: eng
  text: "A graph G=(V, E) is called fully regular if for every independent set I c
    V, the number of vertices in V\\I  that are not connected to any element of I
    depends only on the size of I. A linear ordering of the vertices of G is called
    successive if for every i, the first i vertices induce a connected subgraph of
    G. We give an explicit formula for the number of successive vertex orderings of
    a fully regular graph.\r\nAs an application of our results, we give alternative
    proofs of two theorems of Stanley and Gao & Peng, determining the number of linear
    edge orderings of complete graphs and complete bipartite graphs, respectively,
    with the property that the first i edges induce a connected subgraph.\r\nAs another
    application, we give a simple product formula for the number of linear orderings
    of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for
    every i, the first i hyperedges induce a connected subgraph. We found similar
    formulas for complete (non-partite) 3-uniform hypergraphs and in another closely
    related case, but we managed to verify them only when the number of vertices is
    small."
article_number: '105776'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Lixing
  full_name: Fang, Lixing
  last_name: Fang
- first_name: Hao
  full_name: Huang, Hao
  last_name: Huang
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Gábor
  full_name: Tardos, Gábor
  last_name: Tardos
- first_name: Junchi
  full_name: Zuo, Junchi
  last_name: Zuo
citation:
  ama: Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully
    regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10).
    doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>
  apa: Fang, L., Huang, H., Pach, J., Tardos, G., &#38; Zuo, J. (2023). Successive
    vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>
  chicago: Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive
    Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier, 2023. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>.
  ieee: L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings
    of fully regular graphs,” <i>Journal of Combinatorial Theory. Series A</i>, vol.
    199, no. 10. Elsevier, 2023.
  ista: Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings
    of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.
  mla: Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.”
    <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10, 105776, Elsevier,
    2023, doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>.
  short: L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory.
    Series A 199 (2023).
date_created: 2023-06-25T22:00:45Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-01-30T12:03:51Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jcta.2023.105776
external_id:
  arxiv:
  - '2206.13592'
file:
- access_level: open_access
  checksum: 9eebc213b4182a66063a99083ff5bd04
  content_type: application/pdf
  creator: dernst
  date_created: 2024-01-30T12:03:10Z
  date_updated: 2024-01-30T12:03:10Z
  file_id: '14902'
  file_name: 2023_JourCombinatiorialTheory_Fang.pdf
  file_size: 352555
  relation: main_file
  success: 1
file_date_updated: 2024-01-30T12:03:10Z
has_accepted_license: '1'
intvolume: '       199'
issue: '10'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '10'
oa: 1
oa_version: Published Version
publication: Journal of Combinatorial Theory. Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Successive vertex orderings of fully regular graphs
tmp:
  image: /images/cc_by_nc_sa.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
    BY-NC-SA 4.0)
  short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 199
year: '2023'
...
---
_id: '4056'
abstract:
- lang: eng
  text: This paper proves that for every n ≥ 4 there is a convex n-gon such that the
    vertices of 2n - 7 vertex pairs are one unit of distance apart. This improves
    the previously best lower bound of ⌊ (5n - 5) 3⌋ given by Erdo{combining double
    acute accent}s and Moser if n ≥ 17.
acknowledgement: The first author is pleased to acknowledge partial support by the
  Amoco Fnd. Fat. Dev. Comput. Sci. i-6-44862 and the National Science Foundation
  under Grant CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Péter
  full_name: Hajnal, Péter
  last_name: Hajnal
citation:
  ama: Edelsbrunner H, Hajnal P. A lower bound on the number of unit distances between
    the vertices of a convex polygon. <i>Journal of Combinatorial Theory Series A</i>.
    1991;56(2):312-316. doi:<a href="https://doi.org/10.1016/0097-3165(91)90042-F">10.1016/0097-3165(91)90042-F</a>
  apa: Edelsbrunner, H., &#38; Hajnal, P. (1991). A lower bound on the number of unit
    distances between the vertices of a convex polygon. <i>Journal of Combinatorial
    Theory Series A</i>. Elsevier. <a href="https://doi.org/10.1016/0097-3165(91)90042-F">https://doi.org/10.1016/0097-3165(91)90042-F</a>
  chicago: Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of
    Unit Distances between the Vertices of a Convex Polygon.” <i>Journal of Combinatorial
    Theory Series A</i>. Elsevier, 1991. <a href="https://doi.org/10.1016/0097-3165(91)90042-F">https://doi.org/10.1016/0097-3165(91)90042-F</a>.
  ieee: H. Edelsbrunner and P. Hajnal, “A lower bound on the number of unit distances
    between the vertices of a convex polygon,” <i>Journal of Combinatorial Theory
    Series A</i>, vol. 56, no. 2. Elsevier, pp. 312–316, 1991.
  ista: Edelsbrunner H, Hajnal P. 1991. A lower bound on the number of unit distances
    between the vertices of a convex polygon. Journal of Combinatorial Theory Series
    A. 56(2), 312–316.
  mla: Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of Unit
    Distances between the Vertices of a Convex Polygon.” <i>Journal of Combinatorial
    Theory Series A</i>, vol. 56, no. 2, Elsevier, 1991, pp. 312–16, doi:<a href="https://doi.org/10.1016/0097-3165(91)90042-F">10.1016/0097-3165(91)90042-F</a>.
  short: H. Edelsbrunner, P. Hajnal, Journal of Combinatorial Theory Series A 56 (1991)
    312–316.
date_created: 2018-12-11T12:06:41Z
date_published: 1991-03-01T00:00:00Z
date_updated: 2022-03-02T09:56:10Z
day: '01'
doi: 10.1016/0097-3165(91)90042-F
extern: '1'
intvolume: '        56'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/009731659190042F?via%3Dihub
month: '03'
oa: 1
oa_version: Published Version
page: 312 - 316
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2070'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A lower bound on the number of unit distances between the vertices of a convex
  polygon
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 56
year: '1991'
...
---
_id: '4098'
abstract:
- lang: eng
  text: To points p and q of a finite set S in d-dimensional Euclidean space Ed are
    extreme if {p, q} = S ∩ h, for some open halfspace h. Let e2(d)(n) be the maximum
    number of extreme pairs realized by any n points in Ed. We give geometric proofs
    of , if n⩾4, and e2(3)(n) = 3n−6, if n⩾6. These results settle the question since
    all other cases are trivial.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Gerd
  full_name: Stöckl, Gerd
  last_name: Stöckl
citation:
  ama: Edelsbrunner H, Stöckl G. The number of extreme pairs of finite point-sets
    in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>. 1986;43(2):344-349.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>
  apa: Edelsbrunner, H., &#38; Stöckl, G. (1986). The number of extreme pairs of finite
    point-sets in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>
  chicago: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of
    Finite Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series
    A</i>. Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>.
  ieee: H. Edelsbrunner and G. Stöckl, “The number of extreme pairs of finite point-sets
    in Euclidean spaces,” <i>Journal of Combinatorial Theory Series A</i>, vol. 43,
    no. 2. Elsevier, pp. 344–349, 1986.
  ista: Edelsbrunner H, Stöckl G. 1986. The number of extreme pairs of finite point-sets
    in Euclidean spaces. Journal of Combinatorial Theory Series A. 43(2), 344–349.
  mla: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of Finite
    Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series A</i>,
    vol. 43, no. 2, Elsevier, 1986, pp. 344–49, doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>.
  short: H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986)
    344–349.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T14:02:41Z
day: '01'
doi: 10.1016/0097-3165(86)90075-0
extern: '1'
intvolume: '        43'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub
month: '11'
oa: 1
oa_version: None
page: 344 - 349
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2020'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of extreme pairs of finite point-sets in Euclidean spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 43
year: '1986'
...
---
_id: '4103'
abstract:
- lang: eng
  text: Let A be an arrangement of n lines in the plane. Suppose F1,…, Fk are faces
    in the dissection induced by A and that Fi is a t(Fi)-gon. We give asymptotic
    bounds on the maximal sum ∑i=1kt(Fi) which can be realized by k different faces
    in an arrangement of n lines. The results improve known bounds for k of higher
    order than n(1/2).
acknowledgement: The second author thanks Gan Gusfield for useful discussion.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the maximal number of edges of many faces in an
    arrangement. <i>Journal of Combinatorial Theory Series A</i>. 1986;41(2):159-166.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). On the maximal number of edges of
    many faces in an arrangement. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of
    Many Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the maximal number of edges of many faces
    in an arrangement,” <i>Journal of Combinatorial Theory Series A</i>, vol. 41,
    no. 2. Elsevier, pp. 159–166, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. On the maximal number of edges of many faces
    in an arrangement. Journal of Combinatorial Theory Series A. 41(2), 159–166.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of Many
    Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    41, no. 2, Elsevier, 1986, pp. 159–66, doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 41 (1986)
    159–166.
date_created: 2018-12-11T12:06:57Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T09:46:55Z
day: '01'
doi: 10.1016/0097-3165(86)90078-6
extern: '1'
intvolume: '        41'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900786?via%3Dihub
month: '11'
oa: 1
oa_version: Published Version
page: 159 - 166
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2015'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the maximal number of edges of many faces in an arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 41
year: '1986'
...
---
_id: '4113'
abstract:
- lang: eng
  text: Let S denote a set of n points in the Euclidean plane. A subset S′ of S is
    termed a k-set of S if it contains k points and there exists a straight line which
    has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum
    number of k-sets which can be realized by a set of n points. This paper studies
    the asymptotic behaviour of fk(n) as this function has applications to a number
    of problems in computational geometry. A lower and an upper bound on fk(n) is
    established. Both are nontrivial and improve bounds known before. In particular,  is
    shown by exhibiting special point-sets which realize that many k-sets. In addition,  is
    proved by the study of a combinatorial problem which is of interest in its own
    right.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the number of line separations of a finite set
    in the plane. <i>Journal of Combinatorial Theory Series A</i>. 1985;38(1):15-29.
    doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1985). On the number of line separations
    of a finite set in the plane. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations
    of a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1985. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the number of line separations of a finite
    set in the plane,” <i>Journal of Combinatorial Theory Series A</i>, vol. 38, no.
    1. Elsevier, pp. 15–29, 1985.
  ista: Edelsbrunner H, Welzl E. 1985. On the number of line separations of a finite
    set in the plane. Journal of Combinatorial Theory Series A. 38(1), 15–29.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of
    a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    38, no. 1, Elsevier, 1985, pp. 15–29, doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 38 (1985)
    15–29.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T14:14:25Z
day: '01'
doi: 10.1016/0097-3165(85)90017-2
extern: '1'
intvolume: '        38'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 15 - 29
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2011'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of line separations of a finite set in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1985'
...