UPA Perpustakaan Universitas Jember

Drawing Graphs Using a Small Number of Obstacles

BALKO, Martin - Personal Name
CIBULKA, Josef - Personal Name
VALTR, Pavel - Personal Name

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.

EB00000003383K Available

Detail Information

Series Title

Call Number

Publisher

: ,

Collation

Language

ISBN/ISSN

Classification

NONE

Detail Information

Content Type

E-Jurnal

Media Type

Carrier Type

Edition

Subject(s)

Obstacle number
Geometric drawing
Arrangements of line segments

Specific Detail Info

Statement of Responsibility

Martin Balko1,2 · Josef Cibulka1 · Pavel Valtr

No other version available

UPA Perpustakaan

Merupakan Unit Pendukung Akademis (UPA) yang bersama-sama dengan unit lain melaksanakan Tri Dharma Perguruan Tinggi (PT) melalui menghimpun, memilih, mengolah, merawat serta melayankan sumber informasi kepada civitas akademika Universitas Jember khususnya dan masyarakat akademis pada umumnya.

VISI

UPA Perpustakaan Universitas Jember sebagai perpustakaan modern dengan layanan prima yang mampu menunjang visi Universitas Jember.

MISI

Menyelenggarakan pembinaan dan pengembangan ketersediaan bahan pustaka dan informasi ilmiah sesuai dengan kebutuhan pemustaka secara berkelanjutan

Meningkatkan kualitas dan sistem manajemen layanan perpustakaan secara professional dengan memanfaatkan teknologi informasi

Membina dan mengembangkan jaringan kerjasama dengan pusat-pusat informasi dan lembaga terkait dalam dan luar negeri

UPA Perpustakaan Universitas Jember

NPP. 3509212D1000001

Drawing Graphs Using a Small Number of Obstacles

BALKO, Martin - Personal NameCIBULKA, Josef - Personal NameVALTR, Pavel - Personal Name

Series Title

Call Number

Publisher

Collation

Language

ISBN/ISSN

Classification

Content Type

Media Type

Carrier Type

Edition

Subject(s)

Specific Detail Info

Statement of Responsibility

About Us

UPA Perpustakaan

Total Koleksi

Total Item

Total Member

Total Pustakawan

Total Terpinjam

Peminjaman Tahun 2025

Peminjaman 5 Tahun

Peminjaman Bulan June 2025

Total Pengunjung

Pengunjung Tahun 2025

Pengunjung 5 Tahun Terakhir

Pengunjung Bulan June 2025

New collection + Update

tata cara perhitungan dan pelaporan paak penghasilan pasal 23 atas sewa sound system pada lembaga penyiaran publik radio republik indonesia jember

Pelaksanaan Tebu Rakyat Intensifikasi di Wilayah Kerja Pabrik Gula Pesantren Kota Kediri Tahun 1975-1998

proses administrasi pengenaan pajak penghasilan pasal 4 ayat 2 atas jasa pelaksanaan kontruksi atap baja ringan pada pt wijaya pt makarti perkasa jember

pengaruh pemmberian macam suplemen dan media tanam terhadap multiplikasi tunas anggrek

Analisis Muatan Stimulasi Kognitid Pada Lembar Kerja Anak (Lka) Di Kelompok B Tk Bina Anaprasa Nuris Jember

pengaruh dosis pemupukan bokashi terhadap pertumbuhan dan hasil tiga varistas jagung komposit pada sistem agrofortry tanaman karet muda

Aplikasi Android

Our Services

Help Desk and Service Support UPA Perpustakaan

Tautan Pintas :

Jam Layanan :

Senin - Kamis:

Jum'at:

Sabtu dan Minggu:

Alamat & Kontak Info :

Jalan Kalimantan No. 37 - Kampus Bumi Tegalboto Kotak POS 159 Jember, Jawa Timur, 68121, Indonesia

library@unej.ac.id

(+62) 331 333860

BALKO, Martin - Personal Name
CIBULKA, Josef - Personal Name
VALTR, Pavel - Personal Name