BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Onur Çağırıcı

Onur Çağırıcı contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryLogic in Computer Science

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

preprint2020arXiv

Clique-Width of Point Configurations

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On conflict-free chromatic guarding of simple polygons

We study the problem of colouring the vertices of a polygon, such that every viewer in it can see a unique colour. The goal is to minimise the number of colours used. This is also known as the conflict-free chromatic guarding problem with vertex guards, and is motivated, e.g., by the problem of radio frequency assignment to sensors placed at the polygon vertices. We first study the scenario in which viewers can be all points of the polygon (such as a mobile robot which moves in the interior of the polygon). We efficiently solve the related problem of minimising the number of guards and approximate (up to only an additive error) the number of colours required in the special case of polygons called funnels. Then we give an upper bound of O(log^2 n) colours on n-vertex weak visibility polygons, by decomposing the problem into sub-funnels. This bound generalises to all simple polygons. We briefly look also at the second scenario, in which the viewers are only the vertices of the polygon. We show a lower bound of 3 colours in the general case of simple polygons and conjecture that this is tight. We also prove that already deciding whether 1 or 2 colours are enough is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On embeddability of unit disk graphs onto straight lines

Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e. unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be $\exists\mathbb{R}$-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks corresponds to a pair of sensors being able to communicate with one another. It is usually assumed that the nodes have identical sensing ranges, and thus a unit disk graph model is used to model problems concerning wireless sensor networks. We consider the unit disk graph realization problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. In this paper, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either $x$-axis or $y$-axis. Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to $x$-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.

0 citations0 reviewsNo code linkedOpen access