Record Detail
Advanced Search![No image available for this title](./images/default/image.png)
Text
Drawing Graphs Using a Small Number of Obstacles
An obstacle representation of a graph G is a set of points in the plane representing the vertices of G together with a set of polygonal obstacles such that two vertices of G are connected by an edge in G if and only if the line segment between the corresponding points avoids all the obstacles. The obstacle number obs(G) of G is the minimum number of obstacles in an obstacle representation of G We provide the first non-trivial general upper bound on the obstacle number of graphs by showing that every n-vertex graph G satisfies obs(G) ≤ nlog n − n + 1. This refutes a conjecture of Mukkamala, Pach, and Pálvölgyi. For n-vertex graphs with bounded
chromatic number, we improve this bound to O(n). Both bounds apply even when the obstacles are required to be convex We also prove a lower bound 2(hn) on the number of n-vertex graphs with obstacle number at most h for h < n and a lower bound (n4/3M2/3) for the complexity of a collection of M ≥ (n log3/2 n) faces in an arrangement of line segments with n endpoints The latter bound is tight up to a multiplicative constant.
File Attachment
Availability
EB00000003383K | Available |
Detail Information
Series Title |
-
|
---|---|
Call Number |
-
|
Publisher | : ., |
Collation |
-
|
Language | |
ISBN/ISSN |
-
|
Classification |
NONE
|
Content Type |
E-Jurnal
|
Media Type |
-
|
---|---|
Carrier Type |
-
|
Edition |
-
|
Subject(s) | |
Specific Detail Info |
-
|
Statement of Responsibility |
Martin Balko1,2 · Josef Cibulka1 · Pavel Valtr
|
Other version/related
No other version available
OPAC
RECORD DETAIL
Back To Previous
Hari Lahir Pancasila: Ajang Mengenalkan Keragaman Suku Bangsa Budaya Indonesia
Universitas Jember menggelar Upacara Bendera Peringatan Hari Lahir Pancasila 1 Juni 2024. Upacara kali ini memiliki konsep yang berbeda dari tahun sebelumnya. Jika pada tahun sebelumnya hanya jajaran pimpinan yang menggunakan pakaian adat, namun tahun ini Mahasiwa, Dosen dan Tenaga...
BENGKEL SASTRA: MENGASAH BAKAT KEPENULISAN PUISI SANTRI JEMBER
Selasa (28/5), Santri se-Kabupaten Jember melakukan Library Tour di UPA Perpustakaan Universitas Jember. Kegiatan ini termasuk dalam serangkaian acara Bengkel Sastra yang dilaksanakan oleh Balai Bahasa Provinsi Jawa Timur. Kegiatan Bengkel Sastra dengan Tema “Penulisan Puisi Bagi Santri ...
EKSITSPACE: AJANG EKSPRESI SENI DAN LITERASI
Eksitspace kembali digelar pada Senin 27 Mei 2024. Eksitspace kali ini merupakan yang pertama kali digelar pada tahun 2024 yang juga dilaksanakan secara rutin tiap tahunnya. Eksitspace nantinya akan meramaikan lingkungan pepustakaan setiap bulannya dengan menampilkan pertunjukan ...