View in EDS PDF Full Text

Representing Hypergraphs by Point-Line Incidences.

Saved in:
Bibliographic Details
Title: Representing Hypergraphs by Point-Line Incidences.
Authors: Dobler, Alexander1, Mondal, Debajyoti2, Kobourov, Stephen3, Nöllenburg, Martin1
Source: Discrete Mathematics & Theoretical Computer Science (DMTCS). 2026, Vol. 28 Issue 3, p1-24. 24p.
Subjects: Hypergraphs, Polynomial time algorithms, Computational complexity, Incidence geometry, Intersection graph theory
Abstract: We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap, or not. We show ∃ℝ-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends--to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 196705618
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Representing Hypergraphs by Point-Line Incidences.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Dobler%2C+Alexander%22">Dobler, Alexander</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Mondal%2C+Debajyoti%22">Mondal, Debajyoti</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Kobourov%2C+Stephen%22">Kobourov, Stephen</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22Nöllenburg%2C+Martin%22">Nöllenburg, Martin</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Mathematics+%26+Theoretical+Computer+Science+%28DMTCS%29%22">Discrete Mathematics & Theoretical Computer Science (DMTCS)</searchLink>. 2026, Vol. 28 Issue 3, p1-24. 24p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Hypergraphs%22">Hypergraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Incidence+geometry%22">Incidence geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Intersection+graph+theory%22">Intersection graph theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap, or not. We show ∃ℝ-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends--to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=196705618
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 24
        StartPage: 1
    Subjects:
      – SubjectFull: Hypergraphs
        Type: general
      – SubjectFull: Polynomial time algorithms
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Incidence geometry
        Type: general
      – SubjectFull: Intersection graph theory
        Type: general
    Titles:
      – TitleFull: Representing Hypergraphs by Point-Line Incidences.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Dobler, Alexander
      – PersonEntity:
          Name:
            NameFull: Mondal, Debajyoti
      – PersonEntity:
          Name:
            NameFull: Kobourov, Stephen
      – PersonEntity:
          Name:
            NameFull: Nöllenburg, Martin
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: 2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 13658050
          Numbering:
            – Type: volume
              Value: 28
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Discrete Mathematics & Theoretical Computer Science (DMTCS)
              Type: main
ResultId 1