Denmark has advised citizens against travel to Saudi Arabia, amid growing anger across the Muslim world at Danish depictions of the Prophet Muhammad.
Palestinians burned Danish flags on the streets of Gaza
A newspaper that published cartoons of the Prophet, one of which pictured a bomb hidden in his turban, apologised on Monday for offending Muslims.
Islam bans any depiction of the Prophet Muhammad or Allah.
The backlash has included a boycott of Danish goods, diplomatic sanctions, and Islamic militant threats.
The editor of the Jyllands-Posten newspaper told a Jordanian news agency: "These cartoons were not in violation of Danish law but have irrefutably offended many Muslims, and for that we apologise."
The Danish Prime Minister, Anders Fogh Rasmussen, responded: "It delights me enormously that Jyllands-Posten took this evening a very essential step."
But he again refused to apologise himself, and defended the freedom of the press.
"The Danish government cannot apologise on behalf of a Danish newspaper. It does not work like that... and we have explained that to the Arab countries. Independent media are not edited by the government," he said.
The Danish foreign ministry advised against non-essential travel to Saudi Arabia and urged Danes to be cautious in other Muslim countries.
THE ROW SO FAR
30 January: Gunmen raid EU's Gaza office (pictured)
29 January: Libya says it will close its embassy in Denmark
28 January: Danish company Arla places advertisements in Mid-East newspapers trying to stop a boycott
26 January: Saudi Arabia recalls its ambassador
20 January: Ambassadors in Denmark of 10 Muslim countries complain to the Danish PM
"Danes who choose to stay in Saudi Arabia should show extraordinarily high watchfulness," it said on its website.
Saudi Arabia has recalled its ambassador to Denmark, while Libya said it was closing its embassy in Copenhagen.
On Monday masked gunmen briefly stormed the local office of the EU in Gaza, demanding apologies from Denmark and Norway, where a paper reprinted the cartoons.
The Danish Red Cross said it had pulled two employees out of Gaza, following a threat from the militant al-Aqsa Martyrs Brigades, Reuters reported.
A statement on the internet purporting to be from an Iraqi militant group called on fighters to "hit whatever targets possible belonging to these two countries and others that follow their steps".
Meanwhile pan-Arab organisations have begun efforts to reach a UN resolution, backed by possible sanctions, to protect religions from insults.