Publication

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Fabrizio Frati
2011
Article
Résumé

We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K-2,K-n, one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or poly-line grid drawing. Combining the two results, the Omega(n2(root log n)) area lower bound is achieved.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (24)
Volume englobant
Dans les domaines de la synthèse d'image et de la géométrie algorithmique, un volume englobant pour un ensemble d'objets est un volume fermé qui contient entièrement l'union de l'ensemble des objets. Les volumes englobants sont utilisés pour améliorer l'efficacité des opérations géométriques en utilisant des volumes simples, qui contiennent des objets beaucoup plus complexes. Normalement, plus un volume est simple plus le test de chevauchement est simple. Les volumes englobants sont le plus souvent utilisés pour accélérer certains types de tests.
Minimum bounding box
In geometry, the minimum or smallest bounding or enclosing box for a point set S in N dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box". The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation.
Problème de la clique
thumb|upright=1.5|Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets. En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées.
Afficher plus
Publications associées (20)

Social-Transmotion: Promptable Human Trajectory Prediction

Alexandre Massoud Alahi, Yang Gao, Kaouther Messaoud Ben Amor, Saeed Saadatnejad

Accurate human trajectory prediction is crucial for applications such as autonomous vehicles, robotics, and surveillance systems. Yet, existing models often fail to fully leverage the non-verbal social cues human subconsciously communicate when navigating ...
2024

Rigidity-Aware Detection for 6D Object Pose Estimation

Mathieu Salzmann, Yinlin Hu, Jingyu Li, Rui Song

Most recent 6D object pose estimation methods first use object detection to obtain 2D bounding boxes before actually regressing the pose. However, the general object detection methods they use are ill-suited to handle cluttered scenes, thus producing poor ...
Los Alamitos2023

Radatron: Accurate Detection Using Multi-resolution Cascaded MIMO Radar

Haitham Al Hassanieh, Junfeng Guan, Seyedsohrab Madani, Saurabh Gupta, Waleed Ahmed

Millimeter wave (mmWave) radars are becoming a more popular sensing modality in self-driving cars due to their favorable characteristics in adverse weather. Yet, they currently lack sufficient spatial resolution for semantic scene understanding. In this pa ...
SPRINGER INTERNATIONAL PUBLISHING AG2022
Afficher plus